hdu 1087 A Plug for UNIX 最大流

题意：http://www.phpfans.net/article/htmls/201012/MzI1MDQw.html

　　1、在一个会议室里有n种插座，每种插座一个；

　　2、每个插座只能插一种以及一个电器（或者适配器）；

　　3、有m个电器，每个电器有一个插头需要插在相应一种插座上；

　　4、不是所有电器都能在会议室找到相应插座；

　　5、有k种适配器，每种适配器可以有无限多数量；

　　6、每种适配器(a, b)可以把b类插座变为a类插座；

　　7、问最后有多少个电器无法使用。

分析：图片来源：http://www.cnblogs.com/longdouhzt/archive/2011/09/03/2165860.html

网上给出的很直观的建图方式。看着很舒心，但是要注意。每种适配器(a, b)可以把b类插座变为a类插座。

在图中，B->X, X->A,X->D是可以的，但是没有反向边。

这个不知道的话，一直错。我以为是自己哪里错掉了。还换了算法做。

SAP: 0MS

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<map>

 #include<algorithm>

 using namespace std;

 const int N=;

 const int M=*N*N, INF=0x3f3f3f3f;

 struct node

 {

     int to,next,w;

 }edge[M];

 int head[N],numh[N],h[N],cure[N],pre[N];

 int ans,tot;

 map<string,int> st;

 void SAP(int s, int e,int n)

 {

     int flow,u,tmp,neck,i;

     ans=;

     for(i=;i<=n;i++)

         cure[i]=head[i];

     numh[]=n;

     u=s;

     while(h[s]<n)

     {

         if(u==e)

         {

             flow =INF;

             for(i=s;i!=e;i=edge[cure[i]].to)

             {

                 if(flow>edge[cure[i]].w)

                 {

                     neck=i;

                     flow =edge[cure[i]].w;

                 }

             }

             for(i=s;i!=e;i=edge[cure[i]].to)

             {

                 tmp=cure[i];

                 edge[tmp].w-=flow;

                 edge[tmp^].w+=flow;

             }

             ans+=flow;

             u=neck;

         }

         for(i=cure[u];i!=-;i=edge[i].next)

             if(edge[i].w && h[u]==h[edge[i].to]+) break;

         if(i!=-) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;}

         else

         {

             if(==--numh[h[u]]) break;

             cure[u]=head[u];

             for(tmp=n,i=head[u];i!=-;i=edge[i].next)

                 if(edge[i].w) tmp=min(tmp, h[edge[i].to]);

             h[u]=tmp+;

             ++numh[h[u]];

             if(u!=s) u=pre[u];

         }

     }

 }

 void init()

 {

     tot=;

     memset(head,-,sizeof(head));

     memset(pre,-,sizeof(pre));

     memset(h,,sizeof(h));

     memset(numh,,sizeof(numh));

     st.clear();

 }

 void addedge(int i,int j,int w)

 {

     edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++;

     edge[tot].to=i;edge[tot].w=;edge[tot].next=head[j];head[j]=tot++;

 }

 char str[],ch[];

 int main()

 {

     //freopen("test.txt","r",stdin);

     int s,e,i,j,k,a,b,c,t;

     init();

     s=;e=;t=;

     scanf("%d",&a);

     for(i=;i<=a;i++){

         scanf("%s",str);

         if(st[str]==)  st[str]=++t;

         addedge(st[str],e,);

     }

     scanf("%d",&b);

     for(i=;i<=b;i++){

         scanf("%s%s",ch,str);

         if(st[ch]==) st[ch]=++t;

         if(st[str]==) st[str]=++t;

         addedge(st[ch],st[str],);

         addedge(s,st[ch],);

     }

     scanf("%d",&c);

     for(i=;i<=c;i++){

         scanf("%s%s",ch,str);

         if(st[ch]==) st[ch]=++t;

         if(st[str]==) st[str]=++t;

         addedge(st[ch],st[str],INF);

         //addedge(st[str],st[ch],INF);

     }

     SAP(s,e,t);

     printf("%d\n",b-ans);

     return ;

 }

EK: 32MS

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<map>

 #include<queue>

 #include<algorithm>

 using namespace std;

 map<string,int> st;

 const int N=, INF=0x3f3f3f3f;

 int Map[N][N],pre[N],n,ans;

 bool vis[N];

 queue<int> que;

 bool EK_bfs(int s,int e)

 {

     int i,k;

     while(!que.empty()) que.pop();

     memset(vis,,sizeof(vis));

     memset(pre,-,sizeof(pre));

     que.push(s);

     vis[s]=;

     while(!que.empty())

     {

         k=que.front();

         if(e==k)  return ;

         que.pop();

         for(i=;i<=n;i++)

         {

             if(Map[k][i]&&!vis[i])

             {

                 vis[i]=;

                 pre[i]=k;

                 que.push(i);

             }

         }

     }

     return ;

 }

 void EK(int s,int e)

 {

     int u,mn;

     ans=;

     while(EK_bfs(s,e))

     {

         mn=INF;

         u=e;

         while(pre[u]!=-)

         {

             mn=min(mn,Map[pre[u]][u]);

             u=pre[u];

         }

         ans+=mn;

         u=e;

         while(pre[u]!=-)

         {

             Map[pre[u]][u]-=mn;

             Map[u][pre[u]]+=mn;

             u=pre[u];

         }

     }

 }

 void init()

 {

     memset(Map,,sizeof(Map));

 }

 char str[],ch[];

 int main()

 {

     //freopen("test.txt","r",stdin);

     int s,e,i,j,k,a,b,c,t;

     init();

     s=;e=;t=;

     scanf("%d",&a);

     for(i=;i<=a;i++){

         scanf("%s",str);

         if(st[str]==)  st[str]=++t;

         Map[st[str]][e]=;

     }

     scanf("%d",&b);

     for(i=;i<=b;i++){

         scanf("%s%s",ch,str);

         if(st[ch]==) st[ch]=++t;

         if(st[str]==) st[str]=++t;

         Map[st[ch]][st[str]]=;

         Map[s][st[ch]]=;

     }

     scanf("%d",&c);

     for(i=;i<=c;i++){

         scanf("%s%s",ch,str);

         if(st[ch]==) st[ch]=++t;

         if(st[str]==) st[str]=++t;

         Map[st[ch]][st[str]]=INF;

         //Map[st[str]][st[ch]]=INF;

     }

     n=t;

     EK(s,e);

     printf("%d\n",b-ans);

     return ;

 }

巴特西

hdu 1087 A Plug for UNIX 最大流

最新文章

热门文章