UVA 1627 UVA 1627 Team them up! （二分图染色+01背包）

痛定思痛。 2021-12-14 18:35 190阅读 0赞

## 题意：n个人要分为两组，每个组都不可以为空，给出这n个人的关系（单向的），要求分完组之后，每个组内的人必须两两都互相认识。问怎么分可以使得两组人数差最小。 ##

## 思路：将非互相认识的人之间建一条无向边，这样n个点可能会分为若干个联通子图，如果某个子图不是二分图则直接无解，对于一个联通的子图进行黑白染色，所以黑白子的个数是固定的，黑子和白字分别分到两个集合里去。然后拿每个联通子图的黑白子数差去做一下背包，最接近0的可行值就是答案。 ##

## LRJ代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 100 + 5;
    int n, G[maxn][maxn], color[maxn], diff[maxn], cc;
    vector<int> team[maxn][2]; // team[cc][c] is the list of people in connected-component cc, color c
    
    // returns false if not bipartite graph
    bool dfs(int u, int c) {
      color[u] = c;
      team[cc][c-1].push_back(u);
      for(int v = 0; v < n; v++) { //实际只能通过不满足联接的条件，来确定另外一个队的点集
        if(u != v && !(G[u][v] && G[v][u])) { // u and v must be in different groups
          if(color[v] > 0 && color[v] == color[u]) return false;
          if(!color[v] && !dfs(v, 3-c)) return false;
        }
      }
      return true;
    }
    
    bool build_graph() {
      memset(color, 0, sizeof(color));
      cc = 0; // current connected-component
      for(int i = 0; i < n; i++)
        if(!color[i]) {
          team[cc][0].clear();
          team[cc][1].clear();
          if(!dfs(i, 1)) return false; //可以保证color[i]为0时，设i为1队并不与已有条件冲突
          diff[cc] = team[cc][0].size() - team[cc][1].size();
          cc++;
        }
        //每一次安排（即cc++），都是通过目前与所有的其他点的安排没有冲突的点来生成的，所\
    以不论+diff[i]或-diff[i]都没问题
      return true;
    }
    
    // d[i][j+n] = 1 iff we can arrange first i cc so that team 1 has j more people than team 2.
    int d[maxn][maxn*2], teamno[maxn];
    
    void print(int ans) {
      vector<int> team1, team2;
      for(int i = cc-1; i >= 0; i--) {
        int t;
        if(d[i][ans-diff[i]+n]) { t = 0; ans -= diff[i]; }
        else { t = 1; ans += diff[i]; }
        for(int j = 0; j < team[i][t].size(); j++)
          team1.push_back(team[i][t][j]);
        for(int j = 0; j < team[i][1^t].size(); j++)
          team2.push_back(team[i][1^t][j]);
      }
      printf("%d", team1.size());
      for(int i = 0; i < team1.size(); i++) printf(" %d", team1[i]+1);
      printf("\n");
    
      printf("%d", team2.size());
      for(int i = 0; i < team2.size(); i++) printf(" %d", team2[i]+1);
      printf("\n");
    }
    
    void dp() {
      memset(d, 0, sizeof(d));
      d[0][0+n] = 1;
      for(int i = 0; i < cc; i++)
        for(int j = -n; j <= n; j++) if(d[i][j+n]) {
          d[i+1][j+diff[i]+n] = 1;
          d[i+1][j-diff[i]+n] = 1;
        }
      for(int ans = 0; ans <= n; ans++) {
        if(d[cc][ans+n]) { print(ans); return; }
        if(d[cc][-ans+n]) { print(-ans); return; }
      }
    }
    
    int main() {
      int T;
      cin >> T;
      while(T--) {
        cin >> n;
        memset(G, 0, sizeof(G));
        for(int u = 0; u < n; u++) {
          int v;
          while(cin >> v && v) G[u][v-1] = 1;
        }
    
        if(n == 1 || !build_graph()) cout << "No solution\n";
        else dp();
    
        if(T) cout << "\n";
      }
      return 0;
    }