| ||||||||||
| 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