Codeforces 68 C. Synchrophasotron

問題

n個の頂点からなる有向グラフが与えられる。
それぞれの辺には最小流量、最大流量、およびコストが定められている。

辺(u,v)に流量cのフローを流した場合、
c＞0ならコスト(u,v)+c^2のコストがかかり、
c=0ならコストはかからない。

1番の頂点からn番の頂点に流量が整数で、かつ最小のフローを流す。
それが複数ある場合、コストが最大のフローを流す。
流量の最小値およびその時のコストの最大値を出力せよ。
ただしフローが流れない場合は-1 -1を出力せよ。

制約条件

n≦6
最小流量,最大流量≦6

方針

フローっぽい問題であるが、コストが流量の線形になっていないため、多項式時間で求めるのは難しそうである。
ここでは制約が小さいので、全探索する。
途中で流量保存則などが満たされていない場合、その時点で枝刈りしてやることで、最大ケースに対しても50msくらいで終わる。

ソースコード

int n;
int l[6][6],h[6][6],a[6][6];
int flow[6][6],total;
int mxcost,cost;

void rec(int c,int e){
  if(e==n){
    int in=0, out=0;
    rep(i,n)in+=flow[i][c], out+=flow[c][i];
    if(c==0&&out==total||c==n-1&&in==total||c!=0&&c!=n-1&&in==out)rec(c+1,c+2);
    return;
  }
  if(c==n){
    mxcost=max(mxcost,cost);
    return;
  }
  for(int i=l[c][e];i<=h[c][e];i++){
    flow[c][e]+=i;
    cost+=(i?a[c][e]:0)+i*i;
    rec(c,e+1);
    cost-=(i?a[c][e]:0)+i*i;
    flow[c][e]-=i;
  }
}

void run(){
  cin>>n;
  rep(i,n*(n-1)/2){
    int s,t,L,H,A;
    cin>>s>>t>>L>>H>>A;
    s--; t--;
    l[s][t]=L;
    h[s][t]=H;
    a[s][t]=A;
  }
  for(total=0;total<=36;total++){
    mxcost=-(int)1e9;
    memset(flow,0,sizeof(flow));
    cost=0;
    rec(0,1);
    if(mxcost>=0){
      cout<<total<<" "<<mxcost<<endl;
      return;
    }
  }
  cout<<-1<<" "<<-1<<endl;
}