AtCoder ABC #214 : H - Collecting

Gよりこちらの方が思いつきやすいかな…。
https://atcoder.jp/contests/abc214/tasks/abc214_h

問題

N点M辺の有向グラフがある。
各点iにはX[i]個のアイテムがある。
頂点1から始め、K人の人がそれぞれ辺にそって移動し、その際経由した点の全アイテムを回収する。
(複数人が同一点を経由しても、複数回回収はできない)

K人の人が最適に移動したとき、回収できる総アイテム数の最大値を求めよ。

解法

まずグラフを強連結成分分解し、縮約しておこう。
そうすると以後DAGについてのみ考えればよくなる。

何もしないと全アイテムをロスするが、初めてある点を通ると、1人目はロス分を回収できる、と考えると、ロス分をコストとみなした最小コストフローとみなすことができる。

以下のようにフローを作ろう。
事前に、頂点をトポロジカルソート順にしておき、X[i](を縮約したもの)の累積和を取っておく。

• 各頂点vは2倍化する。点in(v)→out(v)に、２つの辺を張ろう。１つは容量1・コスト0であり、もう一つは容量無限大、コストは縮約元のX[i]の総和である。
  • これは初めて点vを通る人だけ、コストをX[i]削減できることを意味する。
• out(v)からsinkに対し、容量無限大、コストX[v+1]+X[v+2]+.....分の辺を張る。これは、v以降の移動をあきらめることを意味する。
• 縮約後のグラフでu→vに辺があるとき、out(u)→in(v)に容量無限大、コストX[u+1]+...+X[v-1]の辺を張る。これは縮約後のグラフで辺に沿って移動することを意味する。

あとはK*sum(X)から、上記グラフでフローをK流す場合の最小コストを引けばよい。
これは、コストを最小化、すなわちロスしなくて済む回収分のアイテム数に相当する。

int N,M;
int K;
vector<int> E[202020];
set<int> E2[202020];
int X[202020];
ll S[202020];
class SCC {
public:
	static const int MV = 2025000;
	vector<vector<int> > SC; int NV,GR[MV];
private:
	vector<int> E[MV], RE[MV], NUM; int vis[MV];
public:
	void init(int NV) { this->NV=NV; for(int i=0;i<NV;i++) { E[i].clear(); RE[i].clear();}}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu);
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0,i; SC.clear(); SC.resize(NV); NUM.clear();
		assert(NV);
		FOR(i,NV) vis[i]=0; FOR(i,NV) if(!vis[i]) dfs(i); FOR(i,NV) vis[i]=0;
		for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){
			SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++;
		}
		SC.resize(c);
	}
};

template<int NV,class V> class MinCostFlow {
public:
	struct edge { int to; V capacity; V cost; int reve;};
	vector<edge> E[NV]; int prev_v[NV], prev_e[NV]; V dist[NV]; V pot[NV];
	void add_edge(int x,int y, V cap, V 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 */
	}
	
	V mincost(int from, int to, ll flow) {
		V res=0; int i,v;
		ZERO(prev_v); ZERO(prev_e); fill(pot, pot+NV, 0);
		while(flow>0) {
			fill(dist, dist+NV, numeric_limits<V>::max()/2);
			dist[from]=0;
			priority_queue<pair<V,int> > Q;
			Q.push(make_pair(0,from));
			while(Q.size()) {
				V d=-Q.top().first;
				int cur=Q.top().second;
				Q.pop();
				if(dist[cur]!=d) continue;
				if(d==numeric_limits<V>::max()/2) break;
				FOR(i,E[cur].size()) {
					edge &e=E[cur][i];
					if(e.capacity>0 && dist[e.to]>d+e.cost+pot[cur]-pot[e.to]) {
						dist[e.to]=d+e.cost+pot[cur]-pot[e.to];
						prev_v[e.to]=cur;
						prev_e[e.to]=i;
						Q.push(make_pair(-dist[e.to],e.to));
					}
				}
			}
			
			if(dist[to]==numeric_limits<V>::max()/2) return -1;
			V lc=flow;
			for(v=to;v!=from;v=prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity);
			FOR(i,NV) pot[i]+=dist[i];
			flow -= lc;
			res += lc*pot[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;
	}
};
SCC scc;
MinCostFlow<404040,ll> mcf;
int vis[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	scc.init(N);
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		scc.add_edge(x-1,y-1);
	}
	scc.scc();
	FOR(i,N) {
		cin>>X[i];
		S[scc.GR[i]+1]+=X[i];
		FORR(e,E[i]) if(scc.GR[i]!=scc.GR[e]) E2[scc.GR[i]].insert(scc.GR[e]);
	}
	FOR(i,N) S[i+1]+=S[i];
	
	FOR(i,scc.SC.size()) {
		mcf.add_edge(i*2,i*2+1,1,0);
		mcf.add_edge(i*2,i*2+1,9,S[i+1]-S[i]);
		mcf.add_edge(i*2+1,400001,10,S[N]-S[i+1]);
		FORR(e,E2[i]) {
			mcf.add_edge(i*2+1,e*2,10,S[e]-S[i+1]);
		}
	}
	
	ll ret=K*(S[N]-S[scc.GR[0]])-mcf.mincost(scc.GR[0]*2,400001,K);
	cout<<ret<<endl;
	
	
	
}

まとめ

フローに落とせそうとは思ったけど、すんなりこの形を作れなかった。