只是单纯的为了存模板 = =!
#include<map>#include<vector>#include<set>#include<string>#include<queue>#include<stack>#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int INF = 1111111111;const int maxn = 444;const int maxd = 111111;int nn,mm,kk,cnt;int floyd[maxn][maxn];int array[maxn]; //设备插头数组int array2[maxn]; //插座数组map<string,int>idm; //插座编码vector<string>idv; //插座数组//————————-网络流模板—————————struct Edge{int from,to,cap,flow;//容量 流量Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){};};struct EdmondsKarp{int n,m;vector<Edge>edges;vector<int>G[maxn]; //结点i的第j条边是编号多少int a[maxn];//起点到i的可改进量int p[maxn];void init(int n){for(int i = 0; i < n; i++) G[i].clear();edges.clear();}void AddEdge(int from,int to,int cap){edges.push_back(Edge(from,to,cap,0));edges.push_back(Edge(to,from,0,0)); //反向弧m = edges.size();G[from].push_back(m – 2);G[to].push_back(m – 1);}int Maxflow(int s,int t){int flow = 0;while(true){memset(a,0,sizeof(a));queue<int>Q;Q.push(s);//加入起点a[s] = INF;while(!Q.empty()){int x = Q.front(); Q.pop();for(int i = 0; i < G[x].size(); i++){Edge &e = edges[G[x][i]];if(!a[e.to] && e.cap > e.flow){p[e.to] = G[x][i];//a[e.to] = min(a[x],e.cap – e.flow);Q.push(e.to);}}if(a[t]) break;}if(!a[t]) break;for(int u = t; u != s; u = edges[p[u]].from){edges[p[u]].flow += a[t];edges[p[u]^1].flow -= a[t];}flow += a[t];}return flow;}}edm;//————————————————————void debug(){for(int i = 0; i < idv.size(); i++)cout << idv[i] << endl;for(int i = 1; i < cnt; i++){for(int j = 1; j < cnt; j++)printf("%d ",floyd[i][j]);puts("");}for(int i = 0; i < nn; i++)printf("%d ",array2[i]);puts("");for(int i = 0; i < mm; i++)printf("%d ",array[i]);puts("");}void Floyd(){//利用F loyd判断重复for(int i = 1; i < cnt; i++) floyd[i][i] = 1;for(int k = 1; k < cnt; k++)for(int i = 1; i < cnt; i++)for(int j = 1; j < cnt; j++){if(floyd[i][k] && floyd[k][j])floyd[i][j] = 1;}}void solve(){for(int i = 0; i < mm; i++){//插座for(int j = 0; j < nn; j++){ //插头int e1 = array[i],e2 = array2[j];if(floyd[e1][e2]){//printf("%d %d\n",i + 1,mm + 1 + j);edm.AddEdge(i + 1,mm + 1 + j,INF);}}}for(int i = 0; i < mm; i++){//printf("0 %d\n",i + 1);edm.AddEdge(0,i + 1,1);}for(int i = 0; i < nn; i++){//printf("%d %d\n",mm + 1 + i,nn + mm + 1);edm.AddEdge(mm + 1 + i,nn + mm + 1,1);}int ff = edm.Maxflow(0,nn + mm + 1);printf("%d\n",mm – ff);}int main(){int T;char str[30],str2[30];scanf("%d",&T);while(T–){memset(floyd,0,sizeof(floyd));//initedm.init(422);cnt = 1;idm.clear();idv.clear();scanf("%d",&nn);//插座for(int i = 0; i < nn; i++){scanf("%s",str);string sstr(str);if(!idm[sstr]){idv.push_back(str);idm[sstr] = cnt++;}array2[i] = idm[sstr];}scanf("%d",&mm);//插头for(int i = 0; i < mm; i++){scanf("%*s%s",str);string sstr(str);if(!idm[sstr]){idv.push_back(str);idm[sstr] = cnt++;}array[i] = idm[sstr];}scanf("%d",&kk);for(int i = 0; i < kk; i++){scanf("%s%s",str,str2);string sstr1(str),sstr2(str2);if(!idm[sstr1]){idv.push_back(sstr1);idm[sstr1] = cnt++;}if(!idm[sstr2]){idv.push_back(sstr2);idm[sstr2] = cnt++;}int e1 = idm[sstr1],e2 = idm[sstr2];floyd[e1][e2] = 1;//printf("%d %d\n",e1,e2);}Floyd();//debug();solve();if(T) puts("");}return 0;}
，因害怕失败而不敢放手一搏，永远不会成功
