Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
走投无路,只能贴代码了In Reply To:我就是这样建的图啊,思路一样,死都过不了 Posted by:E09610125 at 2010-07-13 09:11:28 #include<stdio.h> #include<string.h> #include<queue> #define N 815 #define INF 1000000000 using namespace std; int cap[N][N],flow[N][N],p[N],lim[N]; queue<int>q; int mf(int s,int t) { memset(flow,0,sizeof(flow)); int f=0; while(1) { memset(lim,0,sizeof(lim)); lim[s]=INF; q.push(s); while(!q.empty()) { int u=q.front();q.pop(); for(int v=0;v<=t;v++) if(!lim[v]&&cap[u][v]>flow[u][v]) { p[v]=u;q.push(v); lim[v]=lim[u] < cap[u][v]-flow[u][v] ? lim[u] : cap[u][v]-flow[u][v]; } } if(lim[t]==0) break; for(int u=t;u!=s;u=p[u]) { flow[p[u]][u]+=lim[t]; flow[u][p[u]]-=lim[t]; } f+=lim[t]; } return f; } char rec[815][30],de[30]; int main() { int n,m,k; int i,j; while(scanf("%d",&n)!=EOF) { memset(cap,0,sizeof(cap)); for(i=1;i<=n;i++) { scanf("%s",rec[i]); cap[0][i]=1; } scanf("%d",&m); int top=n+1; for(i=1;i<=m;i++) { scanf("%s %s",de,rec[top]); bool find=0; for(j=1;j<top;j++) if(strcmp(rec[top],rec[j])==0) {find=1;cap[j][i]=INF;break;} if(!find) {cap[top][i]=INF;top++;} } scanf("%d",&k); char ma[30],re[30]; int s1,e; for(i=0;i<k;i++) { scanf("%s %s",ma,re); int find=0; for(j=1;j<top;j++) if(strcmp(rec[j],re)==0) {find=1;s1=j;break;} if(!find) {strcpy(rec[top],re);s1=top++;} for(find=0,j=1;j<top;j++) if(strcmp(ma,rec[j])==0) {find=1;e=j;break;} if(!find) {strcpy(rec[top],ma);e=top++;} cap[s1][e]=INF; } for(i=1;i<=m;i++) cap[i][top]=1; int ans=m-mf(0,top); printf("%d\n",ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator