本文共 2854 字，大约阅读时间需要 9 分钟。
题目描述：有N个电器每个电器可以插到相应的插座上 M个插座还有 无限多的插座转换器可以将插座转换成其他型号
构图：源点到每个电器连一条权值为1的边，每个电器与相应插座连1边，相应插座与插座之间连INF边，含有的插座与汇点连相应权值的边。
xiaodai的模板！！！这个模板1的位置不能放源点汇点，可以放在0，2；
#include #include #include #include #include #include using namespace std;#define N 1200#define M 50220#define INF 0x3f3f3f3fclass MaxFlow {public: struct record { int v, f, next; } edge[M]; int n, s, t; int pos[N], dis[N], vh[N], cl; int his[N], di[N], pre[N]; void AddEdge(int a, int b, int f) { cl++; edge[cl].next = pos[a]; edge[cl].v = b; edge[cl].f = f; pos[a] = cl; cl++; edge[cl].next = pos[b]; edge[cl].v = a; edge[cl].f = 0; //若为无向边，则f = f pos[b] = cl; } void Init() { cl = 1; memset(dis, 0, sizeof(dis)); memset(vh, 0, sizeof(vh)); memset(pos, 0, sizeof(pos)); } int flow() { vh[0] = n; //初始化GAP数组（默认所有点的距离标号均为0，则距离标号为0的点数量为n） for (int i = 0; i < n; i++) di[i] = pos[i]; //初始化当前弧 int i = s, aug = INF, flow = 0; //初始化一些变量，flow为全局流量，aug为当前增广路的流量 bool flag = false; //标记变量，记录是否找到了一条增广路（若没有找到则修正距离标号） while (dis[s] < n) { his[i] = aug; //保存当前流量 flag = false; for (int p=di[i]; p; p=edge[p].next) if ((edge[p].f > 0) && (dis[edge[p].v] + 1 == dis[i])) { //利用距离标号判定可行弧 //printf("%d %d\n",i,edge[p].f); flag = true; //发现可行弧 di[i] = p; //更新当前弧 aug = min(aug, edge[p].f); //更新当前流量 pre[edge[p].v] = p; //记录前驱结点 i = edge[p].v; //在弧上向前滑动 if (i == t) { //遇到汇点，发现可增广路 flow += aug; //更新全局流量 //printf("%d\n",flow); while (i != s) { //减少增广路上相应弧的容量，并增加其反向边容量 edge[pre[i]].f -= aug; edge[pre[i]^1].f += aug; i = edge[pre[i]^1].v; } aug = INF; } break; } if (flag) continue; //若发现可行弧则继续，否则更新标号 int min = n - 1; for (int p=pos[i]; p; p=edge[p].next) if ((edge[p].f > 0) && (dis[edge[p].v] < min)) { di[i] = p; //不要忘了重置当前弧 min = dis[edge[p].v]; } --vh[dis[i]]; if (vh[dis[i]] == 0) break; //更新vh数组，若发现距离断层，则算法结束（GAP优化） dis[i] = min + 1; ++vh[dis[i]]; if (i != s) { //退栈过程 i = edge[pre[i]^1].v; aug = his[i]; } } return flow; }} net;int n, b, g[1002][22], s[22];int main() { map now; map ::iterator iter; string temp,t1,t2; int top,ans; while(scanf("%d",&n)!=EOF) { now.clear();net.Init(); top=2; net.s=0,net.t=2; while(n--) { cin>>temp; iter=now.find(temp); if(iter==now.end()) now[temp]=1; else iter->second++; } for(iter=now.begin();iter!=now.end();iter++) { net.AddEdge(++top,2,iter->second); iter->second=top; } scanf("%d",&n); ans=n; while(n--) { cin>>t1>>t2; iter=now.find(t2); if(iter==now.end()) now[t2]=++top; net.AddEdge(++top,now.find(t2)->second,1); net.AddEdge(0,top,1); } scanf("%d",&n); while(n--) { cin>>t1>>t2; iter=now.find(t1); if(iter==now.end()) now[t1]=++top; iter=now.find(t2); if(iter==now.end()) now[t2]=++top; net.AddEdge(now.find(t1)->second,now.find(t2)->second,INF); } net.n=top; printf("%d\n",ans-net.flow()); } return 0;}
转载于:https://www.cnblogs.com/acahesky/p/3223945.html