bzoj 3931 网络吞吐量

Posted on | Views:

最大流.

先跑最短路,求出可以用的边.

边没有流量限制,但点有流量限制,可以将每个点拆成入点和出点,两者间连流量为原来那个点的流量的边.

对于可以用的边 $(u,v)$ ,就将 $u$ 的入点和 $v$ 的出点连起来, $u$ 的出点和 $v$ 的入点连起来,容量均为 $\infty$ .

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
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int inf=1e9;
const ll INF=1e18;
const int MAXN=1024,MAXM=3e5+10;
int n,m,vis[MAXN];
typedef pair<ll,int> pli;
#define mp make_pair
priority_queue<pli> q;
queue<int> Q;
struct Graph
{
	struct Edge
	{
		int u,v,w;
		Edge(int u=0,int v=0,int w=0):u(u),v(v),w(w) {}
	}E[MAXM<<1];
	int tot,ecnt,cur[MAXN],head[MAXN],to[MAXM<<1],nx[MAXM<<1],flow[MAXM<<1];
	Graph(){tot=0;ecnt=1;}
	void addedge(int u,int v,int w)
	{
		E[++tot]=Edge(u,v,w);
		++ecnt;
		to[ecnt]=v;
		nx[ecnt]=head[u];
		flow[ecnt]=w;
		head[u]=ecnt;
	}
	void ins(int u,int v,int w)
	{
		addedge(u,v,w);
		addedge(v,u,0);
	}
	void Dijkstra(ll *dis,int S)
	{
		for(int i=1;i<=n;++i)
			dis[i]=INF,vis[i]=0;
		dis[S]=0;
		q.push(mp(-dis[S],S));
		while(!q.empty())
		{
			int u=(q.top()).second;
			q.pop();
			if(vis[u])
				continue;
			vis[u]=1;
			for(int i=head[u];i;i=nx[i])
			{
				int v=to[i];
				if(dis[v]-dis[u]>flow[i])
				{
					dis[v]=dis[u]+flow[i];
					q.push(mp(-dis[v],v));
				}
			}
		}
	}
	int dep[MAXN];
	bool bfs(int S,int T)
	{
		for(int i=1;i<=2*n;++i)
			dep[i]=-1,cur[i]=head[i];
		dep[S]=0;
		Q.push(S);
		while(!Q.empty())
		{
			int u=Q.front();
			Q.pop();
			for(int i=head[u];i;i=nx[i])
				if(flow[i]>0)
				{
					int v=to[i];
					if(dep[v]==-1)
					{
						dep[v]=dep[u]+1;
						Q.push(v);
					}
				}
		}
		return dep[T]!=-1;
	}
	ll dfs(int u,int T,int limit)
	{
		if(u==T || !limit)
			return limit;
		int f,Flow=0;
		for(int &i=cur[u];i;i=nx[i])
		{
			int v=to[i];
			if(dep[v]==dep[u]+1 && (f=dfs(v,T,min(limit,flow[i]))))
			{
				Flow+=f;
				limit-=f;
				flow[i]-=f;
				flow[i^1]+=f;
				if(!limit)
					break;
			}
		}
		return Flow;
	}
	ll Maxflow(int S,int T)
	{
		ll res=0;
		while(bfs(S,T))
			res+=dfs(S,T,inf);
		return res;
	}
}G1,G2;
ll ds[MAXN],dt[MAXN];
int main()
{
	n=read(),m=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read(),w=read();
		G1.addedge(u,v,w);
		G1.addedge(v,u,w);
	}
	G1.Dijkstra(ds,1);
	G1.Dijkstra(dt,n);
	int S=1,T=n+n;
	for(int i=1;i<=n;++i)
	{
		int c=read();
		G2.ins(i+n,i,c);
		G2.ins(i,i+n,c);
	}	
	for(int i=1;i<=2*m;++i)
	{
		int u=G1.E[i].u,v=G1.E[i].v,w=G1.E[i].w;
		if(ds[u]+w+dt[v]==ds[n])
			G2.ins(u,v+n,inf);
	}
	ll ans=G2.Maxflow(S,T);
	cout<<ans<<endl;
	return 0;
}