「poj2125」Destroying the Graph 破坏图 - 最小割 | Bill Yang's Blog
0%

「poj2125」Destroying the Graph 破坏图 - 最小割

题目大意

    Alice和Bob在玩这样一种游戏:首先,Alice画一个$N$个顶点$M$条边的有向图,然后让Bob删去图中所有的边。规则是每步Bob选择一个顶点,然后或者所有指向这个顶点的有向边被删去(操作一),或者所有以这个顶点为起始的有向边被删去(操作二)。 Alice分配两种代价到每一个顶点: $W_i+$和$W_i-$. 如果Bob对顶点$i$执行操作一,那么他将花费$W_i+$,反之他将花费$W_i-$请你试着帮Bob找出删去图中所有边的最小花费。


题目分析

将点拆成两个,分别表示入与出。
将源点$S\rightarrow i$的容量设为$W_i-$,将$i\rightarrow$汇点$T$的容量设为$W_i+$。
对于题目给出的有向边,容量为$inf$。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=205;

struct Edge {
int from,to,cap,flow;
Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
};

struct Dinic {
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxn];
bool vst[maxn];
int dist[maxn],cur[maxn];
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v) {
edges.push_back(Edge(x,y,v,0));
edges.push_back(Edge(y,x,0,0));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool bfs() {
memset(vst,0,sizeof(vst));
memset(dist,0,sizeof(dist));
queue<int>Q;
Q.push(t); //反向层次图
vst[t]=1;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int id:G[Now]) {
Edge& e=edges[id^1];
int Next=e.from;
if(!vst[Next]&&e.cap>e.flow) {
vst[Next]=1;
dist[Next]=dist[Now]+1;
Q.push(Next);
}
}
}
return vst[s];
}
int dfs(int Now,int a) {
if(Now==t||a==0)return a;
int flow=0;
for(int& i=cur[Now]; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(dist[Now]-1!=dist[Next])continue;
int nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
e.flow+=nextflow;
edges[G[Now][i]^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
int flow=0;
while(bfs()) {
memset(cur,0,sizeof(cur));
flow+=dfs(s,INT_MAX);
}
return flow;
}
} dinic;

int n,m;

int main() {
n=Get_Int();
m=Get_Int();
int S=2*n+1,T=2*n+2;
dinic.init(2*n+2);
for(int i=1; i<=n; i++)dinic.AddEdge(n+i,T,Get_Int());
for(int i=1; i<=n; i++)dinic.AddEdge(S,i,Get_Int());
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
dinic.AddEdge(x,n+y,INT_MAX/2);
}
printf("%d\n",dinic.maxflow(S,T));
return 0;
}
姥爷们赏瓶冰阔落吧~