1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<string>  5 #include<map>  6 #include<algorithm>  7 using namespace std;  8   9 const int N=1010; 10 const int M=2*N*N, INF=0x3f3f3f3f; 11 struct node 12 { 13     int to,next,w; 14 }edge[M]; 15 int head[N],numh[N],h[N],cure[N],pre[N]; 16 int ans,tot; 17 map<string,int> st; 18 void SAP(int s, int e,int n) 19 { 20     int flow,u,tmp,neck,i; 21     ans=0; 22     for(i=1;i<=n;i++) 23         cure[i]=head[i]; 24     numh[0]=n; 25     u=s; 26     while(h[s]<n) 27     { 28         if(u==e) 29         { 30             flow =INF; 31             for(i=s;i!=e;i=edge[cure[i]].to) 32             { 33                 if(flow>edge[cure[i]].w) 34                 { 35                     neck=i; 36                     flow =edge[cure[i]].w; 37                 } 38             } 39             for(i=s;i!=e;i=edge[cure[i]].to) 40             { 41                 tmp=cure[i]; 42                 edge[tmp].w-=flow; 43                 edge[tmp^1].w+=flow; 44             } 45             ans+=flow; 46             u=neck; 47         } 48         for(i=cure[u];i!=-1;i=edge[i].next) 49             if(edge[i].w && h[u]==h[edge[i].to]+1) break; 50         if(i!=-1) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;} 51         else 52         { 53             if(0==--numh[h[u]]) break; 54             cure[u]=head[u]; 55             for(tmp=n,i=head[u];i!=-1;i=edge[i].next) 56                 if(edge[i].w) tmp=min(tmp, h[edge[i].to]); 57             h[u]=tmp+1; 58             ++numh[h[u]]; 59             if(u!=s) u=pre[u]; 60         } 61     } 62 } 63 void init() 64 { 65     tot=0; 66     memset(head,-1,sizeof(head)); 67     memset(pre,-1,sizeof(pre)); 68     memset(h,0,sizeof(h)); 69     memset(numh,0,sizeof(numh)); 70     st.clear(); 71  72 } 73 void addedge(int i,int j,int w) 74 { 75     edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++; 76     edge[tot].to=i;edge[tot].w=0;edge[tot].next=head[j];head[j]=tot++; 77 } 78 char str[30],ch[30]; 79 int main() 80 { 81     //freopen("test.txt","r",stdin); 82     int s,e,i,j,k,a,b,c,t; 83     init(); 84     s=1;e=2;t=2; 85     scanf("%d",&a); 86     for(i=1;i<=a;i++){ 87         scanf("%s",str); 88         if(st[str]==0)  st[str]=++t; 89         addedge(st[str],e,1); 90     } 91     scanf("%d",&b); 92     for(i=1;i<=b;i++){ 93         scanf("%s%s",ch,str); 94         if(st[ch]==0) st[ch]=++t; 95         if(st[str]==0) st[str]=++t; 96         addedge(st[ch],st[str],1); 97         addedge(s,st[ch],1); 98     } 99     scanf("%d",&c);100     for(i=1;i<=c;i++){101         scanf("%s%s",ch,str);102         if(st[ch]==0) st[ch]=++t;103         if(st[str]==0) st[str]=++t;104         addedge(st[ch],st[str],INF);105         //addedge(st[str],st[ch],INF);106     }107     SAP(s,e,t);108     printf("%d\n",b-ans);109     return 0;110 }

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<map> 6 #include<queue> 7 #include<algorithm> 8 using namespace std; 9 map<string,int> st;10 const int N=510, INF=0x3f3f3f3f;11 int Map[N][N],pre[N],n,ans;12 bool vis[N];13 queue<int> que;14 bool EK_bfs(int s,int e)15 {16     int i,k;17     while(!que.empty()) que.pop();18     memset(vis,0,sizeof(vis));19     memset(pre,-1,sizeof(pre));20     que.push(s);21     vis[s]=1;22     while(!que.empty())23     {24         k=que.front();25         if(e==k)  return 1;26         que.pop();27         for(i=1;i<=n;i++)28         {29             if(Map[k][i]&&!vis[i])30             {31                 vis[i]=1;32                 pre[i]=k;33                 que.push(i);34             }35         }36     }37     return 0;38 }39 void EK(int s,int e)40 {41     int u,mn;42     ans=0;43     while(EK_bfs(s,e))44     {45         mn=INF;46         u=e;47         while(pre[u]!=-1)48         {49             mn=min(mn,Map[pre[u]][u]);50             u=pre[u];51         }52         ans+=mn;53         u=e;54         while(pre[u]!=-1)55         {56             Map[pre[u]][u]-=mn;57             Map[u][pre[u]]+=mn;58             u=pre[u];59         }60     }61 }62 void init()63 {64     memset(Map,0,sizeof(Map));65 }66 char str[30],ch[30];67 int main()68 {69     //freopen("test.txt","r",stdin);70     int s,e,i,j,k,a,b,c,t;71     init();72     s=1;e=2;t=2;73     scanf("%d",&a);74     for(i=1;i<=a;i++){75         scanf("%s",str);76         if(st[str]==0)  st[str]=++t;77         Map[st[str]][e]=1;78     }79     scanf("%d",&b);80     for(i=1;i<=b;i++){81         scanf("%s%s",ch,str);82         if(st[ch]==0) st[ch]=++t;83         if(st[str]==0) st[str]=++t;84         Map[st[ch]][st[str]]=1;85         Map[s][st[ch]]=1;86     }87     scanf("%d",&c);88     for(i=1;i<=c;i++){89         scanf("%s%s",ch,str);90         if(st[ch]==0) st[ch]=++t;91         if(st[str]==0) st[str]=++t;92         Map[st[ch]][st[str]]=INF;93         //Map[st[str]][st[ch]]=INF;94     }95     n=t;96     EK(s,e);97     printf("%d\n",b-ans);98     return 0;99 }