[UVa] 10330 - Power Transmission

題目網址: https://goo.gl/NJpxea

題意:
(from luckycat)


解法:
很明顯就是求最大流，建圖的方法稍為注意。
TAG: Dinic, maxflow,

注意:

程式碼:

	/**
	* Tittle: 10330 - Power Transmission
	* Author: Cheng-Shih, Wong
	* Date: 2015/06/28
	*/
	// include files
	#include <bits/stdc++.h>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 205
	#define INF 1e8
	class Edge {
	public:
	int u, v;
	int c;
	int nxt;
	Edge( int _u=-1, int _v=-1, int _c=0, int _nxt=-1 ) {
	u = _u;
	v = _v;
	c = _c;
	nxt = _nxt;
	}
	};
	typedef queue<int> QI;
	typedef vector<int> VI;
	typedef vector<Edge> VE;
	// declarations
	VE edge;
	int ehead[N];
	int n, m;
	int b, d;
	int S, T;
	// functions
	void addEdge( int u, int v, int c )
	{
	int es = edge.size();
	edge.push_back( Edge( u, v, c, ehead[u] ) );
	ehead[u] = es;
	edge.push_back( Edge( v, u, 0, ehead[v] ) );
	ehead[v] = es+1;
	}
	int dinic( int s, int t )
	{
	static int i, now, flow, nxt, ne, minf, mine;
	static int cur[N], dep[N];
	flow = 0;
	while( true ) {
	clr( dep, -1 );
	dep[s] = 0;
	QI que;
	que.push(s);
	while( !que.empty() && dep[t]==-1 ) {
	now = que.front(); que.pop();
	for( ne=ehead[now]; ne!=-1; ne=edge[ne].nxt ) {
	nxt = edge[ne].v;
	if( !edge[ne].c || dep[nxt]!=-1 ) continue;
	dep[nxt] = dep[now]+1;
	que.push(nxt);
	if( nxt==t ) break;
	}
	}
	if( dep[t] == -1 ) break;
	memcpy( cur, ehead, sizeof(ehead) );
	now = s;
	VI stk;
	while( true ) {
	if( now == t ) {
	for( minf=INF, i=0; i<stk.size(); ++i )
	if( minf > edge[stk[i]].c )
	minf = edge[stk[mine=i]].c;
	for( i=0; i<stk.size(); ++i ) {
	edge[stk[i]].c -= minf;
	edge[stk[i]^1].c += minf;
	}
	now = edge[stk[mine]].u;
	stk.resize(mine);
	flow += minf;
	}
	for( ne=cur[now]; ne!=-1; ne=cur[now]=edge[ne].nxt )
	if( edge[ne].c && dep[now]+1==dep[edge[ne].v] ) break;
	if( cur[now]!=-1 ) {
	stk.push_back(cur[now]);
	now = edge[cur[now]].v;
	} else {
	if( stk.empty() ) break;
	dep[now] = -1;
	now = edge[stk.back()].u;
	stk.pop_back();
	}
	}
	}
	return flow;
	}
	void init( void )
	{
	int u, v, c;
	S = n*2+1; T = n*2+2;
	clr( ehead, -1 );
	edge.clear();
	FOR( i, 1, n ) {
	scanf( "%d", &c );
	addEdge( i, i+n, c );
	}
	scanf( "%d", &m );
	FOR( i, 1, m ) {
	scanf( "%d%d%d", &u, &v, &c );
	addEdge( u+n, v, c );
	}
	scanf( "%d%d", &b, &d );
	FOR( i, 1, b ) {
	scanf( "%d", &u );
	addEdge( S, u, INF );
	}
	FOR( i, 1, d ) {
	scanf( "%d", &u );
	addEdge( u+n, T, INF );
	}
	}
	// main function
	int main( void )
	{
	// input
	while( scanf( "%d", &n )==1 ) {
	init();
	printf( "%d\n", dinic(S,T) );
	}
	return 0;
	}

view raw 10330 - Power Transmission.cpp hosted with ❤ by GitHub