AOJ 2561: Revenge of Minimum Cost Flow

ネタバレ：Minimum Cost Flowは必要なかった。

全部 ai > biのときは、分岐するのが無駄と分かるので最短路。
ai < biが一本あっても別にそこを流れる流量を決めうちすればよい。
↑の流量の候補は実は定数個らしくて決めうちを上手くやればWarshall-Floydでも余裕らしい。なるほどね。

サンプルが異常に弱くて ai < bi があるケースが1個しかない。何事。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct edge{
	int t,a,b,d;
	edge(){}
	edge(int t,int a,int b,int d):t(t),a(a),b(b),d(d){}
};
vector<edge>g[120];
vector<edge>rev[120];
int w[120][120];
int ijk[120][5];
int v[120][5];
int main(){
	int n,m,s,t,f;
	scanf("%d%d%d%d%d",&n,&m,&s,&t,&f);
	int cnt=0;
	int p,q;
	int A,B,D;
	for(int i=0;i<m;i++){
		int a,b,c,d,e;
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
		g[a].push_back(edge(b,c,d,e));
		rev[b].push_back(edge(a,c,d,e));
		if(c<d){
			cnt++;
			p=a;
			q=b;
			A=c;B=d;D=e;
		}
	}
	for(int i=0;i<n;i++)for(int j=0;j<n;j++){
		if(i==j)w[i][j]=0;
		else w[i][j]=999999999;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<g[i].size();j++){
			if(g[i][j].a<g[i][j].b)continue;
			w[i][g[i][j].t]=min(w[i][g[i][j].t],g[i][j].a*min(f,g[i][j].d)+g[i][j].b*max(0,f-g[i][j].d));
		}
	}
	for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++){
		w[i][j]=min(w[i][j],w[i][k]+w[k][j]);
	}
	if(cnt==0){
		if(w[s][t]>888888888)printf("Impossible\n");
		else printf("%d\n",w[s][t]);
		return 0;
	}
	int ret=w[s][t];
	for(int i=1;i<=f;i++){
		int co=A*min(i,D)+B*max(0,i-D);
		for(int j=0;j<n;j++)for(int k=0;k<5;k++){
			v[j][k]=0;
			ijk[j][k]=999999999;
		}
		priority_queue<pair<int,pair<int,int> > >Q;
		ijk[p][3]=0;
		ijk[q][4]=0;
		Q.push(make_pair(0,make_pair(p,3)));
		Q.push(make_pair(0,make_pair(q,4)));
		while(Q.size()){
			int cost=-Q.top().first;
			int at=Q.top().second.first;
			int type=Q.top().second.second;
			Q.pop();
			if(v[at][type])continue;
			v[at][type]=1;
			if(type==3){
				for(int j=0;j<rev[at].size();j++){
					if(rev[at][j].a<rev[at][j].b)continue;
					int to=rev[at][j].t;
					int c1=rev[at][j].a*min(i,rev[at][j].d)+rev[at][j].b*max(0,i-rev[at][j].d);
					if(!v[to][type]&&ijk[to][type]>cost+c1){
						ijk[to][type]=cost+c1;
						Q.push(make_pair(-ijk[to][type],make_pair(to,type)));
					}
				}
			}else{
				for(int j=0;j<g[at].size();j++){
					if(g[at][j].a<g[at][j].b)continue;
					int to=g[at][j].t;
					int c1=g[at][j].a*min(i,g[at][j].d)+g[at][j].b*max(0,i-g[at][j].d);
					if(!v[to][type]&&ijk[to][type]>cost+c1){
						ijk[to][type]=cost+c1;
						Q.push(make_pair(-ijk[to][type],make_pair(to,type)));
					}
				}
			}
		}
		if(i==f&&ijk[s][3]<888888888&&ijk[t][4]<888888888){
			ret=min(ret,co+ijk[s][3]+ijk[t][4]);
		}
		ijk[s][0]=0;
		Q.push(make_pair(0,make_pair(s,0)));
		while(Q.size()){
			int cost=-Q.top().first;
			int at=Q.top().second.first;
			int type=Q.top().second.second;
			Q.pop();
			if(v[at][type])continue;
			v[at][type]=0;
			for(int j=0;j<g[at].size();j++){
				if(g[at][j].a<g[at][j].b)continue;
				int to=g[at][j].t;
				int c1=g[at][j].a*min(f,g[at][j].d)+g[at][j].b*max(0,f-g[at][j].d);
				int c2=g[at][j].a*min(f-i,g[at][j].d)+g[at][j].b*max(0,f-i-g[at][j].d);
				if(type==1)swap(c1,c2);
				if(!v[to][type]&&ijk[to][type]>cost+c1){
					ijk[to][type]=cost+c1;
					Q.push(make_pair(-ijk[to][type],make_pair(to,type)));
				}
			}
			int c3=ijk[at][3];
			if(type==1)c3=ijk[at][4];
			if(type<2&&!v[at][type+1]&&ijk[at][type+1]>cost+c3){
				ijk[at][type+1]=cost+c3;
				Q.push(make_pair(-ijk[at][type+1],make_pair(at,type+1)));
			}
		}
		//printf("%d: %d %d\n",i,ijk[t][2],co);
		ret=min(ret,ijk[t][2]+co);
	}
	if(ret>888888888)printf("Impossible\n");
	else printf("%d\n",ret);

}