QUPC2014 : H - お風呂は気持ちいい

風呂とフローでかけてたのか…。
http://qupc2014.contest.atcoder.jp/tasks/qupc2014_h

問題

M個の点のうち、G個の点で無限にエネルギーが生成される。
また、ある点からある点に流すことができるエネルギー量が与えられる。
0番の点にP以上のエネルギーを流せるか答えよ。

解法

最初のG点にはsourceから容量無限の辺を張り、後は最大フローを解くだけ。

int N,M,P,G;
int L[101];

class MaxFlow {
public:
	struct edge { int to, capacity, reve;};
	static const int MV = 10000;
	vector<edge> E[MV];
	int vis[MV];
	
	void init() { for(int i=0;i<MV;i++) E[i].clear();}
	MaxFlow() {init();}
	void add_edge(int x,int y, int cap) {
		E[x].push_back((edge){y,cap,E[y].size()});
		E[y].push_back((edge){x,0, E[x].size()-1}); /* rev edge */
	}
	
	int dfs(int from,int to,int cf) {
		int i,tf;
		if(from==to) return cf;
		vis[from]=1;
		FOR(i,E[from].size()) {
			edge& e=E[from][i];
			if(vis[e.to]==0 && e.capacity>0 && (tf = dfs(e.to,to,min(cf,e.capacity)))>0) {
				e.capacity -= tf;
				E[e.to][e.reve].capacity += tf;
				return tf;
			}
		}
		return 0;
	}
	
	int maxflow(int from, int to) {
		int fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,1<<29))==0) return fl;
			fl+=tf;
		}
	}
};


void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>M>>P>>G;
	
	MaxFlow mf;
	FOR(i,G) {
		cin>>x;
		mf.add_edge(0,x,1<<30);
	}
	FOR(i,N) {
		cin>>x>>y>>j;
		if(y==0) y=101;
		mf.add_edge(x,y,j);
	}
	
	if(mf.maxflow(0,101)>=P) _P("Yes\n");
	else _P("No\n");
}

まとめ

いまいち何がしたい問題だったのかわからない…。