题意：

让n个点和m个点对应，一个n只能对应一个m,一个m可以对应多个n,对每个n给出他能对应的m点集合，求m对应n多数的最小值。

分析：

网络流+二分。

代码：

//poj 2289
//sep9
#include 
  
     
#include 
   
     using namespace std; const int maxN=2048; const int maxM=1000000; struct Edge { int v,f,nxt; }e[maxM*2+10]; queue
    
      que; int src,sink; int g[maxN+10]; int nume; bool vis[maxN+10]; int dist[maxN+10]; int map[2048][2048]; int n,m; char tmp[4000]; void addedge(int u,int v,int c) { e[++nume].v=v;e[nume].f=c;e[nume].nxt=g[u];g[u]=nume; e[++nume].v=u;e[nume].f=0;e[nume].nxt=g[v];g[v]=nume; } void init() { memset(g,0,sizeof(g)); nume=1; } void bfs() { while(!que.empty()) que.pop(); vis[src]=true; que.push(src); while(!que.empty()){ int u=que.front();que.pop(); for(int i=g[u];i;i=e[i].nxt) if(e[i].f&&!vis[e[i].v]){ que.push(e[i].v); dist[e[i].v]=dist[u]+1; vis[e[i].v]=true; } } } int dfs(int u,int delta) { if(u==sink) return delta; int ret=0; for(int i=g[u];delta&&i;i=e[i].nxt) if(e[i].f&&dist[e[i].v]==dist[u]+1){ int dd=dfs(e[i].v,min(e[i].f,delta)); e[i].f-=dd; e[i^1].f+=dd; delta-=dd; ret+=dd; } return ret; } int dinic(int maxx) { init(); src=0,sink=n+m+1; int i,j; for(i=1;i<=n;++i) addedge(src,i,1); for(i=1;i<=n;++i) for(j=1;j<=m;++j) if(map[i][j]==1) addedge(i,n+j,1); for(i=1;i<=m;++i) addedge(n+i,sink,maxx); int ret=0; while(1){ memset(vis,0,sizeof(vis)); memset(dist,0,sizeof(dist)); bfs(); if(!vis[sink]) break; ret+=dfs(src,INT_MAX); } if(ret==n) return 1; return 0; } int main() { while(scanf("%d%d",&n,&m)==2){ if(n==0&&m==0) break; int i,j; getchar(); memset(map,0,sizeof(map)); for(int i=1;i<=n;i++) { gets(tmp); int len=strlen(tmp); for(int j=0;j
     
      ='0'&&tmp[j]<='9') { int v=0; while(tmp[j]>='0'&&tmp[j]<='9') { v=v*10+tmp[j++]-'0'; } map[i][v+1]=1; } } } int ans,l,r; l=0,r=n+1; while(l