AOJ 2230: How to Create a Good Game

双対とって最小費用流。

なかなかいろいろなものが得られた。
・双対のやり方…知らないとどうしようもない。
・出てきた形…フローを表す式も知らないとわかりにくい
・特殊な形の最小費用流…負コストがあり、最小流量制限があり、そして全体として流す量には制限がない。ライブラリが負コストにどう対応しているのかも知る機会になる。

全体としてとてもいい問題だと思いました。

#include<string.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<stdio.h>
using namespace std;
namespace MCF {

}
int G[110][110];
int inf=99999999;
vector<pair<int,int> >g[110];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)for(int j=0;j<a;j++){
		if(i!=j)G[i][j]=999999999;
	}
	for(int i=0;i<b;i++){
		int p,q,r;
		scanf("%d%d%d",&p,&q,&r);
		g[p].push_back(make_pair(q,r));
		G[p][q]=-r;
	}
	for(int k=0;k<a;k++)for(int i=0;i<a;i++)for(int j=0;j<a;j++)
		G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
	MCF::init(a+2);
	int s=a;
	int t=a+1;
	MCF::ae(s,a-1,inf,-G[0][a-1]);
	MCF::ae(0,t,inf,0);
	for(int i=0;i<a;i++){
		for(int j=0;j<g[i].size();j++){
			MCF::ae(g[i][j].first,i,inf,-g[i][j].second);
			MCF::ae(g[i][j].first,i,1,-g[i][j].second-100000000);
		}
	}
	MCF::solve(s,t,100000);
//	printf("%lld\n",MCF::toc);
	printf("%d\n",(MCF::toc+(long long)b*100000000)%100000000);
}