题意：给你一张二分图，求右边点到汇点的最小容量（保证流量为n）是多少
题解:二分答案，每次重新建边跑最大流，看是不是为n就好了
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define fi first #define se second #define mp make_pair #define pb push_back #define pii pair<int,int> #define C 0.5772156649 #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1using namespace std;const double g=10.0,eps=1e-12; const int N=2000+10,maxn=500000+10,inf=0x3f3f3f3f;struct edge{int to,Next,c; }e[maxn<<2]; int cnt,head[N]; int dis[N],num; pii pa[maxn<<1]; void add(int u,int v,int c) {// cout<<u<<" "<<v<<" "<<c<<endl;e[cnt].to=v;e[cnt].c=c;e[cnt].Next=head[u];head[u]=cnt++;e[cnt].to=u;e[cnt].c=0;e[cnt].Next=head[v];head[v]=cnt++; } bool bfs(int s,int t) {memset(dis,-1,sizeof dis);dis[s]=0;queue<int>q;q.push(s);while(!q.empty()){int x=q.front();q.pop();if(x==t)return 1;for(int i=head[x];~i;i=e[i].Next){int te=e[i].to;if(dis[te]==-1&&e[i].c>0){dis[te]=dis[x]+1;q.push(te);}}}return 0; } int dfs(int x,int mx,int t) {if(x==t)return mx;int flow=0;for(int i=head[x];~i;i=e[i].Next){int te=e[i].to,f;if(dis[te]==dis[x]+1&&e[i].c>0&&(f=dfs(te,min(mx-flow,e[i].c),t))){e[i].c-=f;e[i^1].c+=f;flow+=f;}}if(!flow)dis[x]=-2;return flow; } int maxflow(int s,int t) {int ans=0,f;while(bfs(s,t)){while((f=dfs(s,inf,t)))ans+=f;}return ans; } void init() {cnt=0;memset(head,-1,sizeof head); } char p[N]; int n,m; int getnum(int l,int r) {int ans=0;for(int i=l;i<=r;i++)ans=ans*10+p[i]-'0';return ans; } bool ok(int x,int s,int t) {init();for(int i=0;i<num;i++)add(pa[i].fi,pa[i].se,1);for(int i=1;i<=m;i++)add(i+n,t,x);return maxflow(s,t)>=n; } int main() {while(~scanf("%d%d",&n,&m)){if(!n&&!m)break;int s=n+m+1,t=n+m+2;num=0;for(int i=1;i<=n;i++)pa[num++]=mp(s,i);getchar();for(int i=1;i<=n;i++){gets(p);int len=strlen(p),j=0;while(j<len&&p[j]!=' ')j++;j++;for(;j<len;j++){int k=j;while(k+1<len&&p[k+1]!=' ')k++;int res=getnum(j,k)+1;pa[num++]=mp(i,res+n);j=k+1;}}int l=0,r=n+1;while(r-l>1){int m=(l+r)/2;if(ok(m,s,t))r=m;else l=m;}printf("%d\n",r);}return 0; } /****************************************/
