Codeforces ECR #055 : G. Petya and Graph

このフローの使い方毎度慣れない。
https://codeforces.com/contest/1082/problem/G

問題

点と辺に数値が設定されている無向グラフが与えられる。
部分グラフのうち、(辺の数値の総和)-(頂点の数値の総和)の最大値を求めよ。

解法

最大フローの形に持ち込んで解く。
まず以下の形でフローを作ろう。

• 元グラフの辺に相当する頂点を作り、sourceから各頂点に辺の設定値分の容量の辺を張る。
• 元グラフの頂点に相当する頂点を作り、そこからsinkに各頂点辺の設定値分の容量の辺を張る。
• 前者の頂点から、両端の点に相当する後者の頂点に、容量無限の辺を張る。

辺の設定値の総和から、このグラフの最大フローを引いたものが解。

これはどういうことか考えてみる。
普通元グラフで辺を張るには、両端の点の設定値を上回るメリットがないと、辺を張るのをあきらめた方がよい、と考える。
この考えを変えて、辺を張ってもよいが、両端の点の設定値が辺の設定値を上回ると、辺を張るメリットを吸収されると考えよう。
そうすると、辺を張ることはデメリットにならない。
同一の頂点を端点するいくつかの辺を張ることで結果的にその頂点のデメリットを上回るメリットを手に入れられるなら良しとする。

そう考えると最大フローに持ち込める。
つまり、基本的に全辺張るのが前提で、しかしそのため頂点を部分グラフに含めることでどの程度吸収されてしまうかという最大値を求めることになる。
上記のとおり、辺のメリットより頂点のデメリットの方が大きくても、設定値の差はマイナスにはならない（フローが流れる量は辺の設定値が最大のため）のでガンガン流す方が良い。

template<class V> class MaxFlow_dinic {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 5100;
	vector<edge> E[MV];
	int itr[MV],lev[MV];
	void add_edge(int x,int y,V cap,bool undir=false) {
		E[x].push_back((edge){y,(int)E[y].size(),cap});
		E[y].push_back((edge){x,(int)E[x].size()-1,undir?cap:0});
	}
	void bfs(int cur) {
		MINUS(lev);
		queue<int> q;
		lev[cur]=0;
		q.push(cur);
		while(q.size()) {
			int v=q.front(); q.pop();
			ITR(e,E[v]) if(e->cap>0 && lev[e->to]<0) lev[e->to]=lev[v]+1, q.push(e->to);
		}
	}
	V dfs(int from,int to,V cf) {
		if(from==to) return cf;
		for(;itr[from]<E[from].size();itr[from]++) {
			edge* e=&E[from][itr[from]];
			if(e->cap>0 && lev[from]<lev[e->to]) {
				V f=dfs(e->to,to,min(cf,e->cap));
				if(f>0) {
					e->cap-=f;
					E[e->to][e->reve].cap += f;
					return f;
				}
			}
		}
		return 0;
	}
	V maxflow(int from, int to) {
		V fl=0,tf;
		while(1) {
			bfs(from);
			if(lev[to]<0) return fl;
			ZERO(itr);
			while((tf=dfs(from,to,numeric_limits<V>::max()))>0) fl+=tf;
		}
	}
};

int N,M;
MaxFlow_dinic<ll> mf;
int A[10101];
int X[10101],Y[10101],R[10101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	FOR(i,N) {
		cin>>A[i];
		mf.add_edge(i,1001,A[i]);
	}
	ll S=0;
	FOR(i,M) {
		cin>>X[i]>>Y[i]>>R[i];
		S+=R[i];
		X[i]--;
		Y[i]--;
		mf.add_edge(1002,1003+i,R[i]);
		mf.add_edge(1003+i,X[i],1LL<<32);
		mf.add_edge(1003+i,Y[i],1LL<<32);
	}
	
	ll ret=mf.maxflow(1002,1001);
	cout<<S-ret<<endl;
	
	
}

まとめ

最初他人のコード見て理解できなかったが、こう考えるとしっくりくるな。