想法都是二分答案。
我的想法是跑网络流,建图。
还有一种想法是,多重匹配。即在匹配时增加匹配数的判断。
这是很有趣的。
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()); } }