spoj 839 Optimal Marks （最小割）
zjhl2
posted @ 2016年7月31日 00:51
with tags
最小割
, 585 阅读
这是《最小割模型在信息学竞赛中的应用》里的一道例题。
从二进制考虑，每个二进制位都用最小割来求解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 | #include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=505,M=3005,INF=0x3f3f3f3f;const int mxN=N,mxM=M*4+2*N;int n,m;int lx[M],ly[M];int v[N];bool mk[N];int p;struct graph{ int S,T; int base[mxN],vec[mxM],pre[mxM],tot; int c[mxM]; int d[mxN],q[mxN]; bool vis[mxN]; void init() { memset(base,0,sizeof(base)); tot=1; } void link(int x,int y,int z) { vec[++tot]=y; pre[tot]=base[x]; base[x]=tot; c[tot]=z; vec[++tot]=x; pre[tot]=base[y]; base[y]=tot; c[tot]=0; } void build() { S=0; T=n+1; for (int i=1;i<=m;i++) link(lx[i],ly[i],1),link(ly[i],lx[i],1); for (int i=1;i<=n;i++) { if (!mk[i]) continue; if (v[i]&1<<p) link(S,i,INF); else link(i,T,INF); } } void update(int u) { vis[u]=1; v[u]|=1<<p; for (int now=base[u];now;now=pre[now]) { int v=vec[now]; if (vis[v]||c[now]==0) continue; update(v); } } void work() { for (int i=S;i<=T;i++) vis[i]=0; update(S); } bool bfs() { int head=0,tail=0; memset(d,-1,sizeof(d)); d[S]=0; q[++tail]=S; while(head<tail) { head++; int u=q[head]; for (int now=base[u];now;now=pre[now]) { int v=vec[now]; if (d[v]==-1&&c[now]>0) { d[v]=d[u]+1; q[++tail]=v; if (v==T) return 1; } } } return 0; } int dfs(int u,int flow) { int r=0; if (u==T) return flow; for (int now=base[u];now&&r<flow;now=pre[now]) { int v=vec[now]; if (c[now]>0&&d[v]==d[u]+1) { int x=min(c[now],flow-r); x=dfs(v,x); r+=x; c[now]-=x; c[now^1]+=x; } } if (!r)d[u]=-2; return r; } int dinic() { int ans=0; while(bfs()) ans+=dfs(S,INF); return ans; }}G;void read(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) mk[i]=0,v[i]=0; for (int i=1;i<=m;i++) scanf("%d%d",&lx[i],&ly[i]); int k; scanf("%d",&k); for (int i=1;i<=k;i++) { int x; scanf("%d",&x); mk[x]=1; scanf("%d",&v[x]); }}int main(){ int t; scanf("%d",&t); while(t--) { read(); for (p=0;p<31;p++) { G.init(); G.build(); G.dinic(); G.work(); } for (int i=1;i<=n;i++) printf("%d\n",v[i]); }} |
评论 (0)
