首页 > 代码库 > Poj 1112 Team Them Up!

Poj 1112 Team Them Up!

2024-07-05 09:05:37   229人阅读

题意：现在有一群人，告诉你每个人都认识哪些人，让你将这一群人分成两组，其中每一组中的每个人都相互认识，并且使得两组中的人数尽量相近。问你是否能分成这样两组，如果不能输出No Solution ，否则输出人数最相近的方案。

注意你认识我不代表我认识你，组中的每一个人都必须是相互认识的。

首先建立由人和人认识关系构成的有向图，然后将其转化成一张无向图，如果两个点之间的边不是双向的，等于没有，所以就将其删去，保留双向边。然后对这个无向图求一次补图，形成的补图可能有多个联通块，并且位于不同联通块中的点是肯定可以放在一个组内的。

之后对于每个联通块，做一次二分图染色判定，判断其是否可以构成一张二分图。为什么要这么做，因为每个联通块中相邻的点是肯定不能放到一个组当中的，所以要对联通块做一次01染色，看看是否可以把当前的联通块分成两组，每一组中的人都不是相邻的。如果做完染色后发现该联通块不能构成一个二分图，那么肯定是No Solution，因为所有人都必须不是属于组1就是属于组2

做染色的同时统计每个联通块中奇点和偶点的数量，然后就可以来做背包了。建立一个容量为n/2的背包，对于每个联通块，我可以取里面所有的奇点也可以取里面所有的偶点，最后递归输出结果。

 

#include <cstdio>
#include <sstream>
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <cctype>
#include <ctime>
#include <set>
#include <climits>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cmath>
#include <string>
#include <list>

#define INPUT_FILE "in.txt"
#define OUTPUT_FILE "out.txt"

using namespace std;

typedef long long LL;
const int INF = INT_MAX / 2;

void setfile() {
    freopen(INPUT_FILE,"r",stdin);
    freopen(OUTPUT_FILE,"w",stdout);
}

const int maxn = 105;

struct Node {
    int cnt,e[maxn],col;
};

Node node[maxn];
bool know[maxn],conflict,team1[maxn],vis[maxn];
bool g[maxn][maxn],dp[maxn * 2][maxn * 2];
int n,sz[maxn],sz_zero[maxn],sz_one[maxn],rcnt;
int pid[maxn][maxn];

//染色
void dfs(int now,int id) {
    if(node[now].col == 0) sz_zero[id]++;
    else sz_one[id]++;
    pid[id][sz[id]++] = now;
    for(int i = 0;i < node[now].cnt;i++) {
        int nowid = node[now].e[i];
        if(node[nowid].col == -1) {
            node[nowid].col = node[now].col ^ 1;
            dfs(nowid,id);
        } else {
            if(node[nowid].col == node[now].col) {
                conflict = true;
            }
        }
    }
}

//统计联通块并且进行染色
void judge() {
    rcnt = 0;
    for(int i = 1;i <= n;i++) {
        if(node[i].col == -1) {
            node[i].col = 0;
            rcnt++;
            dfs(i,rcnt);
        }
    }
}

//将第i个联通块中颜色为col的点加入组中
void addteam(int i,int col) {
    vis[i] = true;
    if(node[i].col == col) {
        team1[i] = true;
    }
    for(int j = 0;j < node[i].cnt;j++) {
        int chid = node[i].e[j];
        if(vis[chid] == false) {
            addteam(chid,col);
        }
    }
}

//输出答案
void print_path(int i,int now) {
    if(i == 0) return;
    if(dp[i - 1][now - sz_zero[i]]) {
        memset(vis,0,sizeof(vis));
        addteam(pid[i][0],0);
        print_path(i - 1,now - sz_zero[i]);
    } else {
        memset(vis,0,sizeof(vis));
        addteam(pid[i][0],1);
        print_path(i - 1,now - sz_one[i]);
    }
}


void work() {
    dp[0][0] = true;
    //背包
    for(int i = 1;i <= rcnt;i++) {
        for(int j = 0;j <= n;j++) {
            if(dp[i - 1][j] == true) {
                dp[i][j + sz_zero[i]] = true;
                dp[i][j + sz_one[i]] = true;
            }
        }
    }
    int val = -1;
    for(int j = n / 2;j >= 1;j--) {
        if(dp[rcnt][j] == true) {
            val = j; break;
        }
    }
    if(val == -1) {
        puts("No solution");
    } else {
        print_path(rcnt,val);
        printf("%d",val);
        for(int i = 1;i <= n;i++) if(team1[i]) printf(" %d",i);
        printf("\n%d",n - val);
        for(int i = 1;i <= n;i++) if(!team1[i]) printf(" %d",i);
        putchar(‘\n‘);
    }
}

int main() {
    int tmp;
    while(scanf("%d",&n) != EOF) {
        memset(node,0,sizeof(node));
        memset(sz,0,sizeof(sz));
        memset(sz_zero,0,sizeof(sz_zero));
        memset(sz_one,0,sizeof(sz_one));
        memset(dp,0,sizeof(dp));
        memset(team1,0,sizeof(team1));
        memset(g,0,sizeof(g));
        //输入并且建立补图
        for(int i = 1;i <= n;i++) {
            while(scanf("%d",&tmp),tmp) {
                g[i][tmp] = true;
            }
            node[i].col = -1;
        }

        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= n;j++) {
                if(!(g[i][j] && g[j][i]) && i != j) {
                    node[i].e[node[i].cnt++] = j;
                }
            }
        }

        //染色并且统计联通块
        conflict = false;
        judge();
        if(conflict) {
            puts("No solution");
        } else {
            work();
        }
    }
    return 0;
}


联系
我们