题目地址：http://poj.org/problem?id=1087 看了一位大佬的代码才过，不愧是我。 题目大意：n个插坐，每种类型只有一个！！！k个插头，类型可以重复！！！，m个插座类型转换器。 其实这是道模板题，我还不会(wsfw)，建好边后套dinic模板。 重点建边： 开始我是正向建边的，后来发现大佬是反向建的，结果我疯狂WA大佬一发就过了。 上图 左边是正向建边，右边是反向建边。 上面提到了，插座是不可以重复的，插头是可以重复的，所以如果正向建边，在插头与e建边的时候就会出现多条路！！！，但每种类型的插座只有一个，故理论上只能计1次，但你同一个插头到e有多条路，就会多计数。反向建边就不会出现这个情况，所以Accepted (没找到绿色溜了溜了) AC代码
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<map> #include<queue> #define MAX 1100 #define inf 0x1f3f3f3f #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; struct node { int to,next,v; }edge[MAX]; struct snode { int first,second; }zhq[MAX]; int head[MAX],cnt,n,m,k,num=1; int vis[MAX]; int s,e; int in[MAX],out[MAX]; map<string,int> mp; void init() { mem(head,-1); cnt=0; e=400; s=0; } void addedge(int from,int to,int value) { edge[cnt]={to,head[from],value}; head[from]=cnt++; } int bfs() { mem(vis,0); queue<int> q; vis[s]=1; q.push(s); while(q.size()) { int u=q.front(); q.pop(); for(int i=head[u];~i;i=edge[i].next) { int to=edge[i].to; if(edge[i].v==0||vis[to]) continue; vis[to]=vis[u]+1; q.push(to); } } return vis[e]; } int dfs(int u,int flow) { if(u==e||flow==0) return flow; for(int i = head[u];i!=-1;i=edge[i].next) { int to =edge[i].to; int v = edge[i].v; if(vis[to]!=vis[u]+1||v==0) continue; int k = dfs(to,min(flow,v)); if(k>0) { edge[i].v-=k; edge[i^1].v+=k; return k; } } return 0; } void dinic() { int ans=0; int k; while(bfs()) { while((k=dfs(s,inf))>0) ans+=k; } printf("%d\n",m-ans); } int main() { init(); cin>>n; getchar(); string a,b; for(int i = 1 ; i<=n;i++) { cin>>a; if(mp[a]==0) mp[a]=num++; addedge(mp[a],e,1); addedge(e,mp[a],0); } cin>>m; getchar(); for(int i = 1 ; i<=m;i++) { cin>>a>>b; if(mp[b]==0) mp[b]=num++; addedge(s,mp[b],1); addedge(mp[b],s,0); } cin>>k; getchar(); for(int i = 1 ; i<=k;i++) { cin>>a>>b; if(mp[a]==0) mp[a]==num++; if(mp[b]==0) mp[b]==num++; zhq[i].first=mp[a]; zhq[i].second=mp[b]; addedge(zhq[i].first,zhq[i].second,inf); addedge(zhq[i].second,zhq[i].first,0); } //build(); dinic(); return 0; }