KUPC2014 : I - Rain

元々本戦参加してないこともあり、自力で解いたか解説見たか思い出せない…。
http://kupc2014.contest.atcoder.jp/tasks/kupc2014_i

問題

N箇所の土地に呪文を使って雨を降らせたい。
呪文はM種類あり、それぞれパラメータA[i],B[i],D[i]で表される。

呪文を1回唱えると、A[i]番の土地に2、B[i]番の土地に0、それ以外の土地に1の雨が降る。
また、その際D[i]の時間がかかる。

初期状態でK種類の呪文C[i]が唱えられたとする。
以後、これらの呪文を任意回数唱え、全ての土地の合計雨量を均等にすることができるか。
出来るなら最小日数を求めよ。

解法

各呪文は、結局A[i]に他より+1、B[i]に他より-1の雨量を増やすものと見なせる。
まずK回呪文を唱えた時点で、一部の土地に雨量の不均一な箇所ができる。
そこでこれらを最小フロー問題に置き換えてよう。

まずK回文の呪文について、
s→B[C[i]]、A[C[i]]→tに容量1、コスト0の辺を張ろう。
ここで張られたB[C[i]]の各土地は雨量が足りないので、ここに雨量が増えるようなフローを流したい。
よってあとM本、A[i]→B[i]に容量無限大、コストD[i]の辺を張る。

そしてs→tに容量Kのフローを流せれば、B[C[i]]の不足分、A[C[i]]の過剰分を埋めるような呪文の割り当てが可能である。
よって最小フローを解けばよい。

class MinCostFlow {
public:
	struct edge { int to, capacity; ll cost, reve;};
	static const int MV = 10010;
	vector<edge> E[MV];
	ll dist[MV], prev_v[MV], prev_e[MV], NV;
	
	MinCostFlow() { init(MV); }
	void init(int NV=MV) { this->NV=NV; for(int i=0;i<MV;i++) E[i].clear();}
	void add_edge(int x,int y, int cap, int cost) {
		E[x].push_back((edge){y,cap,cost,(int)E[y].size()});
		E[y].push_back((edge){x,0, -cost,(int)E[x].size()-1}); /* rev edge */
	}
	
	int mincost(int from, int to, int flow) {
		int res=0,i,v;
		ZERO(prev_v); ZERO(prev_e);
		while(flow>0) {
			fill(dist, dist+NV, 1LL<<50);
			dist[from]=0;
			bool up=true;
			while(up) {
				up=false;
				FOR(v,NV) {
					if(dist[v]==1LL<<50) continue;
					FOR(i,E[v].size()) {
						edge &e=E[v][i];
						if(e.capacity>0 && dist[e.to]>dist[v]+e.cost) {
							dist[e.to]=dist[v]+e.cost;
							prev_v[e.to]=v;
							prev_e[e.to]=i;
							up=true;
						}
					}
				}
			}
			
			if(dist[to]==1LL<<50) return -1;
			int lc=flow;
			for(v=to;v!=from;v=prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity);
			flow -= lc;
			res += lc*dist[to];
			for(v=to;v!=from;v=prev_v[v]) {
				edge &e=E[prev_v[v]][prev_e[v]];
				e.capacity -= lc;
				E[v][e.reve].capacity += lc;
			}
		}
		return res;
	}
};

int N,M,K;
int C[20];
int A[20001],B[20001];


void solve() {
	int f,i,j,k,l,x,y;
	
	MinCostFlow mcf;
	cin>>N>>M>>K;
	FOR(i,K) cin>>C[i];
	FOR(i,M) {
		cin>>A[i]>>B[i]>>j;
		mcf.add_edge(A[i]-1,B[i]-1,15,j);
	}
	FOR(i,K) {
		mcf.add_edge(10000,B[C[i]-1]-1,1,0);
		mcf.add_edge(A[C[i]-1]-1,10001,1,0);
	}
	cout << mcf.mincost(10000,10001,K) <<endl;
}

まとめ

自力じゃこのフローは思いつかなさそうだし、解説見て解いたのかな。