《最小割模型在信息学竞赛中的应用》最优标号

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N=510,M=(3010+N*2)*2,inf=1e9;
 5 int h[N],e[M],ne[M],f[M],idx;
 6 int cur[N],d[N],p[N];
 7 int n,m,S,T;
 8 struct node
 9 {
10     int x,y;
11 }edges[M];
12 int k;
13 void add(int a,int b,int c,int d)
14 {
15     ne[idx]=h[a],e[idx]=b,f[idx]=c,h[a]=idx++;
16     ne[idx]=h[b],e[idx]=a,f[idx]=d,h[b]=idx++;
17 }
18 void bulid(int x)
19 {
20     memset(h,-1,sizeof h);
21     idx=0;
22     for(int i=0;i<m;i++)
23     add(edges[i].x,edges[i].y,1,1);
24     for(int i=1;i<=n;i++)
25         if(p[i])
26         {
27             if(p[i]>>x&1)add(S,i,inf,inf);
28             else add(i,T,inf,inf);
29         }
30 }
31 bool bfs()
32 {
33     memset(d,-1,sizeof d);
34     queue<int>q;
35     q.push(S);
36     d[S]=0;
37     cur[S]=h[S];
38     while(q.size())
39     {
40         int t=q.front();
41         q.pop();
42         for(int i=h[t];i!=-1;i=ne[i])
43         {
44             int j=e[i];
45             if(d[j]==-1&&f[i])
46             {
47                 d[j]=d[t]+1;
48                 cur[j]=h[j];
49                 if(j==T)return true;
50                 q.push(j);
51             }
52         }
53     }
54     return false;
55 }
56 int find(int u,int limit)
57 {
58     if(u==T)return limit;
59     int flow=0;
60     for(int i=cur[u];i!=-1&&flow<limit;i=ne[i])
61     {
62         int j=e[i];
63         cur[u]=i;
64         if(d[j]==d[u]+1&&f[i])
65         {
66             int t=find(j,min(f[i],limit-flow));
67             if(!t)d[j]=-1;
68             f[i]-=t,f[i^1]+=t,flow+=t;
69         }
70     }
71     return flow;
72 }
73 ll dinic(int x)
74 {
75     bulid(x);
76     int r=0,flow;
77     while(bfs())while(flow=find(S,inf))r+=flow;
78     return r;
79 }
80 int main()
81 {
82     S=0,T=N-1;
83     cin>>n>>m;
84     for(int i=0;i<m;i++)scanf("%d%d",&edges[i].x,&edges[i].y);
85     cin>>k;
86     for(int i=0;i<k;i++)
87     {
88         int u,v;
89         scanf("%d%d",&u,&v);
90         p[u]=v;
91     }
92     long long ans=0;
93     for(int i=0;i<31;i++)ans+=dinic(i)<<i;
94     cout<<ans<<endl;
95     return 0;
96 }