【SPOJ839】最优标号

  1 #include <cstdlib>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <cstdio>
  6 #include <queue>
  7 const int maxn=510;
  8 const int maxm=3010;
  9 const int INF=10000*10000;
 10 using namespace std;
 11 struct liu
 12 {
 13        int c,f;
 14        liu(){c=0;f=0;}
 15 }maps[maxn][maxn];
 16 int shu[maxn],map[maxn][maxn];
 17 int bh[maxn],path[maxn],dist[maxn];
 18 
 19 int n,m,k;
 20 long long solve(int times);
 21 void make_maps(int times);
 22 bool BFS();
 23 int dfs(int u,int low);
 24 
 25 int main()
 26 {
 27     int i;
 28     memset(shu,-1,sizeof(shu));
 29     memset(map,0,sizeof(map));
 30     //读入数据 
 31     scanf("%d%d",&n,&m);
 32     for (i=1;i<=m;i++) 
 33     {
 34         int u,v;
 35         scanf("%d%d",&u,&v);
 36         map[u][v]++;
 37         map[v][u]++;
 38     }
 39     scanf("%d",&k);
 40     for (i=1;i<=k;i++) 
 41     {
 42         int u,p;
 43         scanf("%d%d",&u,&p);
 44         shu[u]=p;
 45     }
 46     
 47     long long ans=0;
 48     //注意求解次数 
 49     for (i=0;i<=31;i++) ans+=solve(i);//求解最大流 
 50     printf("%lld",ans);
 51     return 0;
 52 }
 53 //求解函数 
 54 long long solve(int times)
 55 {
 56      int i,flow=0,pos;
 57      
 58      make_maps(times);
 59      while ( BFS() )
 60      {
 61            int now;
 62            while (now=dfs(0,INF)) flow+=now;
 63            //printf("%d\n",now);
 64      }
 65      //printf("%d\n",flow);
 66      return (long long)flow<<times;
 67 }
 68 //构图 
 69 void make_maps(int times)
 70 {
 71      int i,j,bh[maxn];
 72      //-1代表还没有开始标号 
 73      memset(bh,-1,sizeof(bh));
 74      memset(maps,0,sizeof(maps));
 75      for (i=1;i<=n;i++) 
 76      {
 77          if (shu[i]==-1) continue;
 78          bh[i]=((1<<times)&shu[i])==(1<<times);//二进制位
 79          //超级源汇
 80          if (bh[i]!=0) {maps[0][i].f=0;maps[0][i].c=INF;}
 81          else {maps[i][n+1].f=0;maps[i][n+1].c=INF;}
 82      }
 83      for (i=1;i<=n;i++)
 84      for (j=1;j<=n;j++)
 85      {
 86          if (map[i][j]==0) continue;//保留原边 
 87          maps[i][j].c=map[i][j];
 88          maps[i][j].f=0;
 89      }
 90      return;
 91 }
 92 bool BFS()//BFS构建层次网络 
 93 {
 94      int i,u;
 95      queue<int>Q;
 96      memset(dist,-1,sizeof(dist));
 97      dist[0]=0;
 98      Q.push(0);
 99      while (!Q.empty())
100      {
101            int u=Q.front();Q.pop();
102            for (i=0;i<=n+1;i++)
103            {
104                int v=i;
105                if (dist[v]==-1 && maps[u][v].c-maps[u][v].f>0)
106                {
107                    Q.push(v);
108                    dist[v]=dist[u]+1;
109                }
110            }
111      } 
112      return (dist[n+1]!=-1);
113 }
114 int dfs(int v,int low)//增广 
115 {
116     int i;
117     if (v==(n+1) || low==0) return low;
118     int flow=0,f;
119     for (i=0;i<=(n+1);i++)
120     {
121         if (maps[v][i].c-maps[v][i].f>0 && dist[i]==dist[v]+1)
122         {
123             if (f=dfs(i,min(low,maps[v][i].c-maps[v][i].f)))
124             {
125                 maps[v][i].f+=f;
126                 maps[i][v].f-=f;
127                 flow+=f;
128                 low-=f;
129                 if (low==0) break;
130             }
131         } 
132     }
133     return flow;
134 }