Jamie's Contact Groups

想法都是二分答案。
我的想法是跑网络流，建图。
还有一种想法是，多重匹配。即在匹配时增加匹配数的判断。
这是很有趣的。
solution2是多重匹配的匈牙利算法。
注意，我用HK算法实现多重匹配时发现非常慢！！！！所以建议用匈牙利！
solution1：

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int max_n = 5000;
const int max_m = 1e6;
const int inf = 1e9;
vector<int> G[max_n];
struct edge
{
    int to, cap, rev, next;
}E[max_m<<2];
int head[max_n];
int cnt = 1;
void add(int from, int to, int cap) {
    E[cnt].to = to;
    E[cnt].cap = cap;
    E[cnt].rev = cnt + 1;
    E[cnt].next = head[from];
    head[from] = cnt++;
    E[cnt].to = from;
    E[cnt].cap = 0;
    E[cnt].rev = cnt - 1;
    E[cnt].next = head[to];
    head[to] = cnt++;
}

int iter[max_n];
int dist[max_n];
bool searchpath(int s, int t) {
    fill(dist, dist + max_n, -1);
    queue<int> que;dist[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int u = que.front();que.pop();
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (dist[e.to] != -1 || e.cap == 0)continue;
            dist[e.to] = dist[u] + 1;
            que.push(e.to);
        }
    }return dist[t] != -1;
}

int matchpath(int u, int t, int f) {
    if (u == t)return f;
    for (int& i = iter[u];i;i = E[i].next) {
        edge& e = E[i];
        if (dist[e.to] <= dist[u] || e.cap <= 0)continue;
        int d = matchpath(e.to, t, min(e.cap, f));
        if (d > 0) {
            e.cap -= d;
            E[e.rev].cap += d;
            return d;
        }
    }return false;
}

int dinic(int s, int t) {
    int flow = 0;int f;
    while (searchpath(s, t)) {
        for (int i = 1;i < max_n;i++)iter[i] = head[i];
        while (f = matchpath(s, t, inf))
            flow += f;
    }return flow;
}
int n,m;
bool check(int mid){
    int s = n+m+1;int t = s+1;
    fill(head,head+t+5,0);
    cnt=1;
    for (int u=1;u<=n;++u){
        add(s,u,1);
        for (int v=0;v<G[u].size();++v)
            add(u,G[u][v],1);
    }
    for (int u=1+n;u<=m+n;++u)add(u,t,mid);
    return dinic(s,t)==n;
}
int binary(){
    int lft=1;int rgt=n;
    while (lft<rgt){
        int mid = (lft+rgt)>>1;
        if (check(mid))rgt=mid;
        else lft=mid+1;
    }return rgt;
}
int main(){
    char s[100];
    while (scanf("%d %d",&n,&m)){
        if (n==m&&n==0)break;
        for (int u=1,v;u<=n;++u){
            G[u].clear();
            scanf("%s",&s[1]);
            char c;
            while (scanf("%c",&c)){
                if (c=='\n')break;
                scanf("%d",&v);
                G[u].push_back(v+n+1);
            }
        }
        printf("%d\n",binary());
    }
}

solution2:

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int max_n = 3000;
const int max_m = 1e6;
const int inf = 1e9;
vector<int> G[max_n];
struct edge{
    int to,next;
}E[max_m<<1];
int head[max_n];
int cnt=1;
void add(int from,int to){
    E[cnt].to=to;E[cnt].next=head[from];
    head[from]=cnt++;
}
vector<int> rgt_To[max_n];
bool vis[max_n];
bool matchpath(int u,int mid){
    for (int i=head[u];i;i=E[i].next){
        int v = E[i].to;
        if (vis[v])continue;
        vis[v]=1;
        if (rgt_To[v].size()<mid){
            rgt_To[v].push_back(u);
            return true;
        }
        else {
            for (int j=0;j<rgt_To[v].size();++j){
                if (matchpath(rgt_To[v][j],mid)){
                    rgt_To[v][j]=u;
                    return true;
                }
            }
        }
    }return false;
}
int Hungarian(int N,int M,int mid){
    int ans=0;
    for (int i=0;i<=M;++i)rgt_To[i].clear();
    for (int i=1;i<=N;++i){
        fill(vis,vis+M+1,0);
        if (matchpath(i,mid))
            ++ans;
    }return ans==N;
}

int n,m;
int binary(){
    int lft=1;int rgt=n;
    while (lft<rgt){
        int mid = (lft+rgt)>>1;
        if (Hungarian(n,m,mid))rgt=mid;
        else lft=mid+1;
    }return rgt;
}
int main(){
    char s[100];
    while (scanf("%d %d",&n,&m)){
        fill(head,head+n+5,0);
        cnt=1;
        if (n==m&&n==0)break;
        for (int u=1,v;u<=n;++u){
            scanf("%s",&s[1]);
            char c;
            while (scanf("%c",&c)){
                if (c=='\n')break;
                scanf("%d",&v);
                add(u,v+1);
            }
        }
        printf("%d\n",binary());
    }
}