poj 1087 A Plug for UNIX

poj 1087 A Plug for UNIX

#include <iostream>#include <stdio.h>#include <string.h>#include <queue>#include <algorithm>using namespace std;const int maxn = 30000;const int maxm = 50000;const int INF=0x7fffffff;int idx;int cur[maxn], pre[maxn];int dis[maxn], gap[maxn];int aug[maxn], head[maxn];char name[3000][30];int k;struct Node{int u, v, w;int next;}edge[maxm];void addEdge(int u, int v, int w){    edge[idx].u = u;    edge[idx].v = v;    edge[idx].w = w;    edge[idx].next = head[u];    head[u] = idx++;    edge[idx].u = v;    edge[idx].v = u;    edge[idx].w = 0;    edge[idx].next = head[v];    head[v] = idx++;}int sol(char *str){int i;if(k==0){strcpy(name[1],str);k=1;return  1;}for(i=1;i<=k;i++)if(strcmp(name[i],str)==0)return i;k++;strcpy(name[k],str);return k;}int SAP(int s, int e, int n){    int max_flow = 0, v, u = s;    int id, mindis;    aug[s] =INF;    pre[s] = -1;    memset(dis, 0, sizeof(dis));    memset(gap, 0, sizeof(gap));    gap[0] = n; // 我觉得这一句要不要都行，因为dis[e]始终为0    for (int i = 0; i <= n; ++i)   // 初始化当前弧为第一条弧    cur[i] = head[i];    while (dis[s] < n)    {        bool flag = false;        if (u == e)        { max_flow += aug[e]; for (v = pre[e]; v != -1; v = pre[v]) // 路径回溯更新残留网络 {     id = cur[v];     edge[id].w -= aug[e];     edge[id^1].w += aug[e];     aug[v] -= aug[e]; // 修改可增广量，以后会用到     if (edge[id].w == 0) u = v; // 不回退到源点，仅回退到容量为0的弧的弧尾 }        }        for (id = cur[u]; id != -1; id = edge[id].next)        {   // 从当前弧开始查找允许弧 v = edge[id].v; if (edge[id].w > 0 && dis[u] == dis[v] + 1) // 找到允许弧 {     flag = true;     pre[v] = u;     cur[u] = id;     aug[v] = min(aug[u], edge[id].w);     u = v;     break; }        }        if (flag == false)        { if (--gap[dis[u]] == 0) break;  mindis = n; cur[u] = head[u]; for (id = head[u]; id != -1; id = edge[id].next) {     v = edge[id].v;     if (edge[id].w > 0 && dis[v] < mindis)     {         mindis = dis[v];         cur[u] = id; // 修改标号的同时修改当前弧     } } dis[u] = mindis + 1; gap[dis[u]]++; if (u != s) u = pre[u]; // 回溯继续寻找允许弧        }    }    return max_flow;}int main(){    int i,n1,n2,n3;int st,ed;int a,b;char str1[30],str2[30];    while(scanf("%d",&n1)!=EOF)    {idx = 0;        memset(head, -1, sizeof(head));        st=0;k=0;        for(i=1;i<=n1;i++){scanf("%s",str1);a=sol(str1);addEdge(st,a,1);  //源点向插座建边}scanf("%d",&n2);ed=n1+n2+1;for(i=1;i<=n2;i++){scanf("%s %s",str1,str2);a=sol(str1);b=sol(str2);  addEdge(b,a,1);   //插座向电器建立边addEdge(a,ed,1);  //电器向汇点建边}scanf("%d",&n3);for(i=1;i<=n3;i++){scanf("%s %s",str1,str2);a=sol(str1);b=sol(str2);addEdge(b,a,INF);}        printf("%dn",n2-SAP(st, ed, k+2));    }    return 0;}