Day30

Day30

今天学到的是网络流之最大流
好好学习!!!

链式前向星

传送门

网络流之最大流

传送门

Drainage Ditches

Description:
Every time it rains on Farmer John’s fields, a pond forms over Bessie’s favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie’s clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.
Input
The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.
Output
For each case, output a single integer, the maximum rate at which water may emptied from the pond.

1
2
3
4
5
6
7
8
9
Sample Input
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
Sample Output
50

code:

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f;
const ll maxn = 1e6+10;
ll n,m,s,t,u,v,w,cnt;
struct edge{
ll to,dis,nxt;
}G[maxn];
ll head[maxn],d[maxn],cur[maxn];
void add(ll from,ll to,ll dis)
{
G[cnt].to=to;
G[cnt].dis=dis;
G[cnt].nxt=head[from];
head[from]=cnt++;
}
ll dfs(ll u,ll flow)
{
if(u==t) return flow;
ll x=0;
for(ll i=cur[u];i!=-1;i=G[i].nxt)
{
cur[u]=G[i].nxt;
ll v=G[i].to;
if(d[v]==d[u]+1&&G[i].dis>0)
{
ll res=dfs(v,min(flow,G[i].dis));
flow-=res;
x+=res;
G[i].dis-=res;
G[i^1].dis+=res;
if(flow==0) break;
}
}
if(!x) d[u]=-1;
return x;
}
void bfs()
{
memset(d,-1,sizeof(d));
queue<ll> que;
que.push(s);
d[s]=0;
while(!que.empty())
{
ll u=que.front();que.pop();
for(ll i=head[u];i!=-1;i=G[i].nxt)
{
ll v=G[i].to;
if(d[v]==-1&&G[i].dis>0)
{
d[v]=d[u]+1;
que.push(v);
}
}
}
}

void dinic()
{
ll max_flow=0;
while(1)
{
bfs();
if(d[t]==-1) break;
for(ll i=1;i<=n;i++) cur[i]=head[i];
max_flow+=dfs(s,INF);
}
cout<<max_flow<<endl;
}

int main()
{
while(cin>>m>>n)
{
s=1,t=n;
memset(head,-1,sizeof(head));
cnt=0;
for(ll i=0;i<m;i++)
{
cin>>u>>v>>w;
add(u,v,w);
add(v,u,0);
}
dinic();
}
return 0;
}

Island Transport

Description:
In the vast waters far far away, there are many islands. People are living on the islands, and all the transport among the islands relies on the ships.
You have a transportation company there. Some routes are opened for passengers. Each route is a straight line connecting two different islands, and it is bidirectional. Within an hour, a route can transport a certain number of passengers in one direction. For safety, no two routes are cross or overlap and no routes will pass an island except the departing island and the arriving island. Each island can be treated as a point on the XY plane coordinate system. X coordinate increase from west to east, and Y coordinate increase from south to north.
The transport capacity is important to you. Suppose many passengers depart from the westernmost island and would like to arrive at the easternmost island, the maximum number of passengers arrive at the latter within every hour is the transport capacity. Please calculate it.
Input
The first line contains one integer T (1<=T<=20), the number of test cases.
Then T test cases follow. The first line of each test case contains two integers N and M (2<=N,M<=100000), the number of islands and the number of routes. Islands are number from 1 to N.
Then N lines follow. Each line contain two integers, the X and Y coordinate of an island. The K-th line in the N lines describes the island K. The absolute values of all the coordinates are no more than 100000.
Then M lines follow. Each line contains three integers I1, I2 (1<=I1,I2<=N) and C (1<=C<=10000) . It means there is a route connecting island I1 and island I2, and it can transport C passengers in one direction within an hour.
It is guaranteed that the routes obey the rules described above. There is only one island is westernmost and only one island is easternmost. No two islands would have the same coordinates. Each island can go to any other island by the routes.
Output
For each test case, output an integer in one line, the transport capacity.

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
Sample Input
2
5 7
3 3
3 0
3 1
0 0
4 5
1 3 3
2 3 4
2 4 3
1 5 6
4 5 3
1 4 4
3 4 2
6 7
-1 -1
0 1
0 2
1 0
1 1
2 3
1 2 1
2 3 6
4 5 5
5 6 3
1 4 6
2 5 5
3 6 4
Sample Output
9
6

code:

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
#include<bits/stdc++.h.>
using namespace std;
const int N = 100010;
const int INF = 0x3f3f3f3f;
typedef long long ll;
int n,m,start,over;
int deep[N],maxflow;
struct edge{
int to,w,pre;
}a[N<<2];
int cnt=-1,head[N];
void add(int from,int to,int w)
{
a[++cnt].to=to;
a[cnt].w=w;
a[cnt].pre=head[from];
head[from]=cnt;
}
bool bfs()//这里我们不用队列直接用数组代替
{
memset(deep,-1,sizeof(deep));
int q[N<<1];
int fro,bac;
fro=bac=0;
q[bac++]=start,deep[start]=0;
while(fro<bac)
{
int first=q[fro];
if(first==over) return 1;
for(int i=head[first];~i;i=a[i].pre)
{
if(deep[a[i].to]==-1&&a[i].w>0)
{
deep[a[i].to]=deep[first]+1;
q[bac++]=a[i].to;
}
}
fro++;
}
return 0;
}

int dfs(int s,int cap)
{
if(s==over) return cap;
int flow=0,f;
for(int i=head[s];~i;i=a[i].pre)
{
int to=a[i].to;
if(deep[to]==deep[s]+1&&a[i].w)
{
f=dfs(to,min(cap-flow,a[i].w));
a[i].w-=f;
a[i^1].w+=f;
flow+=f;
if(flow==cap) break;
}
}
if(flow==0) deep[s]=-2;
return flow;
}
void dinic()
{
int tem=0;
while(bfs())
while((tem=dfs(start,INF))>0)
maxflow+=tem;
}

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
maxflow=0,cnt=-1;
memset(head,-1,sizeof(head));
scanf("%d %d",&n,&m);
start = over = 1;
int x,y,z,x_min=INF,x_max=-INF;
for(int i=1;i<=n;i++)
{
scanf("%d %d",&x,&y);
if(x<x_min) start=i,x_min=x;
if(x>x_max) over=i,x_max=x;
}
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dinic();
cout<<maxflow<<endl;
}
return 0;
}

Power Network

Description:
A power network consists of nodes (power stations, consumers and dispatchers) connected by power transport lines. A node u may be supplied with an amount s(u) >= 0 of power, may produce an amount 0 <= p(u) <= p max(u) of power, may consume an amount 0 <= c(u) <= min(s(u),c max(u)) of power, and may deliver an amount d(u)=s(u)+p(u)-c(u) of power. The following restrictions apply: c(u)=0 for any power station, p(u)=0 for any consumer, and p(u)=c(u)=0 for any dispatcher. There is at most one power transport line (u,v) from a node u to a node v in the net; it transports an amount 0 <= l(u,v) <= l max(u,v) of power delivered by u to v. Let Con=Σ uc(u) be the power consumed in the net. The problem is to compute the maximum value of Con.
1c1354d5a7c820146d570a7875b230b3.png
An example is in figure 1. The label x/y of power station u shows that p(u)=x and p max(u)=y. The label x/y of consumer u shows that c(u)=x and c max(u)=y. The label x/y of power transport line (u,v) shows that l(u,v)=x and l max(u,v)=y. The power consumed is Con=6. Notice that there are other possible states of the network but the value of Con cannot exceed 6.
Input
There are several data sets in the input. Each data set encodes a power network. It starts with four integers: 0 <= n <= 100 (nodes), 0 <= np <= n (power stations), 0 <= nc <= n (consumers), and 0 <= m <= n^2 (power transport lines). Follow m data triplets (u,v)z, where u and v are node identifiers (starting from 0) and 0 <= z <= 1000 is the value of l max(u,v). Follow np doublets (u)z, where u is the identifier of a power station and 0 <= z <= 10000 is the value of p max(u). The data set ends with nc doublets (u)z, where u is the identifier of a consumer and 0 <= z <= 10000 is the value of c max(u). All input numbers are integers. Except the (u,v)z triplets and the (u)z doublets, which do not contain white spaces, white spaces can occur freely in input. Input data terminate with an end of file and are correct.
Output
For each data set from the input, the program prints on the standard output the maximum amount of power that can be consumed in the corresponding network. Each result has an integral value and is printed from the beginning of a separate line.

1
2
3
4
5
6
7
8
9
10
Sample Input
2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20
7 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)8 (2,3)1 (2,4)7
(3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5)1 (6,0)5
(0)5 (1)2 (3)2 (4)1 (5)4
Sample Output
15
6
Hint
The sample input contains two data sets. The first data set encodes a network with 2 nodes, power station 0 with pmax(0)=15 and consumer 1 with cmax(1)=20, and 2 power transport lines with lmax(0,1)=20 and lmax(1,0)=10. The maximum value of Con is 15. The second data set encodes the network from figure 1.

code:

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
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
const int INF = 0x3f3f3f3f;
const int maxn = 2e5;
using namespace std;
struct edge{
int to,dis,nxt;
}G[maxn];
int head[maxn],d[maxn];
int n,np,nc,m,cnt,s,t;
void add(int from,int to,int dis)
{
G[cnt].to=to;
G[cnt].dis=dis;
G[cnt].nxt=head[from];
head[from]=cnt++;
}
int bfs()
{
memset(d,-1,sizeof(d));
d[s]=0;
queue<int> q;
q.push(s);
while(!q.empty())
{
int u=q.front();
if(u==t) return 1;
q.pop();
for(int i=head[u];i!=-1;i=G[i].nxt)
{
int v=G[i].to;
int dis=G[i].dis;
if(dis&&d[v]==-1)
{
d[v]=d[u]+1;
q.push(v);
}
}
}
return 0;
}
int dfs(int u,int flow)
{
if(u==t) return flow;
int x=0;
for(int i=head[u];i!=-1;i=G[i].nxt)
{
int v=G[i].to;
int dis=G[i].dis;
if(dis&&d[v]==d[u]+1)
{
int f=dfs(v,min(dis,flow-x));
G[i].dis-=f;
G[i^1].dis+=f;
x+=f;
if(x==flow) return x;
}
}
return x;
}
void dinic()
{
int ans=0;
while(bfs())
{
ans+=dfs(s,INF);
}
cout<<ans<<endl;
}
int main()
{
while(~scanf("%d%d%d%d",&n,&np,&nc,&m))
{
cnt=0;
s=n+1;
t=s+1;
memset(head,-1,sizeof(head));
for(int i=0;i<m;i++)
{
int x,y,w;
scanf(" (%d,%d)%d",&x,&y,&w);
add(x,y,w);
add(y,x,0);
}
for(int i=0;i<np;i++)
{
int v,w;
scanf(" (%d)%d",&v,&w);
add(s,v,w);
add(v,s,0);
}
for(int i=0;i<nc;i++)
{
int u,w;
scanf(" (%d)%d",&u,&w);
add(u,t,w);
add(t,u,0);
}
dinic();
}
}

Path

Description:
Years later, Jerry fell in love with a girl, and he often walks for a long time to pay visits to her. But, because he spends too much time with his girlfriend, Tom feels neglected and wants to prevent him from visiting her.
After doing some research on the neighbourhood, Tom found that the neighbourhood consists of exactly n houses, and some of them are connected with directed road. To visit his girlfriend, Jerry needs to start from his house indexed 1 and go along the shortest path to hers, indexed n.
Now Tom wants to block some of the roads so that Jerry has to walk longer to reach his girl’s home, and he found that the cost of blocking a road equals to its length. Now he wants to know the minimum total cost to make Jerry walk longer.
Note, if Jerry can’t reach his girl’s house in the very beginning, the answer is obviously zero. And you don’t need to guarantee that there still exists a way from Jerry’s house to his girl’s after blocking some edges.
Input
The input begins with a line containing one integer T(1≤T≤10), the number of test cases.
Each test case starts with a line containing two numbers n,m(1≤n,m≤10000), the number of houses and the number of one-way roads in the neighbourhood.
m lines follow, each of which consists of three integers x,y,c(1≤x,y≤n,1≤c≤109), denoting that there exists a one-way road from the house indexed x to y of length c.
Output
Print T lines, each line containing a integer, the answer.

1
2
3
4
5
6
7
8
9
Sample Input
1
3 4
1 2 1
2 3 1
1 3 2
1 3 3
Sample Output
3

code:

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
//EK算法求解最大流
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
const ll inf = 34338315071127552;
int n,m,s,t;
struct Node{
ll v;
ll val;
ll next;
}node[20101];
int top=1,head[10101];//top必须从一个奇数开始,一般用-1但我不习惯,解释见下方
void init(int n)
{
memset(head,-1,sizeof(int)*(n+1));
top = 1;
}
inline void addedge(ll u,ll v,ll val){
node[++top].v=v;
node[top].val=val;
node[top].next=head[u];
head[u]=top;
}

inline int Read(){
int x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
ll inque[10101];//点是访问过里
struct Pre{
ll v;//该点的前一个点(从起点过来)
ll edge;//与该点相连的边(靠近起点的)
}pre[10101];
inline bool bfs(){
queue<ll>q;
memset(inque,0,sizeof(inque));
memset(pre,-1,sizeof(pre));
inque[s]=1;
q.push(s);
while(!q.empty()){
ll u=q.front();
q.pop();
for(int i=head[u];i;i=node[i].next){
ll d=node[i].v;
if(!inque[d]&&node[i].val){//node[i].val==0则已经该路径满了
pre[d].v=u;
pre[d].edge=i;
if(d==t)return 1;
inque[d]=1;
q.push(d);
}
}
}
return 0;
}//是否有增广路
ll EK(){
ll ans=0;
while(bfs()){
ll mi=inf;
for(int i=t;i!=s;i=pre[i].v){
mi=min(mi,node[pre[i].edge].val);//每次只能增加增广路上最小的边的权值
}
for(int i=t;i!=s;i=pre[i].v){
node[pre[i].edge].val-=mi;
node[pre[i].edge^1].val+=mi;
//反向的边的编号是正向边的编号^1
//这就是为什么top开始时必须是奇数
}
ans+=mi;
}
return ans;
}
const int maxn = 1e4 + 10;
typedef pair<ll,ll> pii;
vector<pii> G[maxn];
ll dis[maxn];
void djk(int n)
{
for (int i = 0;i <= n+1;i ++) dis[i] = inf;
priority_queue<pii,vector<pii>,greater<pii> > que;
dis[1] = 0;
que.push({0,1});
while (!que.empty())
{
pii p = que.top();
ll v = p.second;
que.pop();
if (dis[v] < p.first) continue;
for (int i = 0;i < G[v].size();i ++)
{
pii p2 = G[v][i];
if (dis[p2.first] > dis[v] + p2.second)
{
dis[p2.first] = dis[v] + p2.second;
que.push({dis[p2.first],p2.first});
}
}
}
}
int main(){
int num;
scanf("%d",&num);
while (num --)
{
//int n,m;
scanf("%d %d",&n,&m);
for (int i = 1;i <= n;i ++)
G[i].clear();
init(n);
for (int i = 1;i <= m;i ++)
{
ll u,v,w;
scanf("%lld %lld %lld",&u,&v,&w);
G[u].push_back({v,w});
}
djk(n);
m = 0;
for (int i = 1;i <= n;i ++)
{
for (int j = 0;j < G[i].size();j ++)
{
pii p = G[i][j];
if (dis[i] + p.second == dis[p.first])
{
//cout<<"u\t"<<i<<"\tv\t"<<p.first<<"\tw\t"<<p.second<<endl;
addedge(i,p.first,p.second);
addedge(p.first,i,0);
m ++;
}
}
}
s = 1,t = n;
ll ans = EK();
printf("%lld\n",ans);
if (!ans) cout<<"dis\t"<<dis[n]<<endl;
}
return 0;
}
//7 8
//1 2 2
//1 3 1
//2 4 1
//3 4 2
//4 5 1
//4 6 2
//5 7 1
//6 7 1

---------------- The End ----------------
0%