【apio 2012】ネットワークフロー

apioは行かなかったが、授業資料は研究に値する.
2~4番の問題はまだあまり見たことがないので、他のいくつかの問題は比較的に年を取っています.
Transform Matrix
mtはwc 2010の校内授業で話したことがありますが、この問題を聞いたことしか覚えていませんが、改めて考えがはっきりしています.まず、任意の1を他の数字に影響を与えずに0に移動することができます.0と仮定すると直接交換します.1であれば、リレーと見なすことができます.1は等価なので、通り抜けることと見なすことができます.では,初期状態の1とターゲット状態の1を1つずつ対応させ,経路の制限をうまく処理すればよいが,この部分は直接最大流にすることができる.
ロード城への道
実はこの問題は省が選ぶ前に私はまだしていなかったが、やり方が奇抜だと聞いただけで、ネットの流れのやり方があるとは思わなかった.私は1つのテーマの性質を無視して、つまりa[i]でh[i]-h[i+1]を表すならば、a[i]-1ならば、きっとあるa[j]+1は費用が異なるだけで(構造することができて、中間hの同昇同降を通じて)、私たちの任務はすべてのaを指定区間[-c,c]に調整することに転換して、調整方式は再分配して1をプラスして1を減らして、しかも費用があって、これは上下境界を伴う最小費用実行フローで実現できる.
この問題は次の問題の構想とは逆に(後で述べる)、主に思想を調整し(これもネットワークストリームの古典的な最適化の面である)、混合図のようなオラ回路は、トラフィックを通じて再分配される.
この問題は元の対偶費用の流れを使って、涛兄の奇抜なアルゴリズムより速く走った.

#include <cstdio>
#include <cstdlib>
#include <cstring>
const long long oo=1073741819102LL;
int s,t,s1,t1,n,m,ss,time;
long long ans,phi;
int tail[100000],v[100000],flag[100000];
int next[2000000],sora[2000000],pow[2000000],st[2000000],p[100000],cost[2000000];
long long flow[2000000],ru[100000],chu[100000],d[100000],tmp,h[100000];
int spfa(int s,int t)
{
  int h,r,i,j,ne,na;
//  memset(d,127,sizeof(d));
  for (i=1;i<=t;i++) d[i]=oo;
  h=r=0;
  st[r=1]=t,d[t]=0,v[t]=1;
  for (;h<r;) {
    ne=st[++h];
    for (i=ne;next[i]!=0;) {
      i=next[i],na=sora[i];
      if (flow[pow[i]] && d[ne]+cost[pow[i]]<d[na]) {
	  d[na]=d[ne]+cost[pow[i]];p[na]=ne;
	if (!v[na]) v[na]=1,st[++r]=na;
      }
    }
    v[ne]=0;
  }
  if (d[s]>=oo) return 0;
  phi+=d[s];
  for (i=1;i<=t;i++) 
    for (j=i;next[j]!=0;) {
      j=next[j],ne=sora[j];
      cost[j]-=d[i]-d[ne];
    }
  return 1;
}
long long dfs(int x,long long low)
{
  if (t1==x) {ans+=phi*low;return low;}
  int i,ne;
  long long sum=0;
  flag[x]=time;
  for (i=x;next[i]!=0;) {
    i=next[i],ne=sora[i];
    if (flow[i] && !cost[i] && flag[ne]!=time) {
      if (flow[i]<low) tmp=dfs(ne,flow[i]);
      else tmp=dfs(ne,low);
      flow[i]-=tmp,flow[pow[i]]+=tmp,sum+=tmp,low-=tmp;
      if (!low) break;
    }
  }
  return sum;
}
void origin()
{
  s=n+1,t=s+1,s1=t+1,t1=s1+1,ss=t1;
  for (int i=1;i<=t1;i++) tail[i]=i,ru[i]=chu[i]=next[i]=0;
}
void link2(int x,int y,long long z,long long c)
{
  ss++,next[tail[x]]=ss,tail[x]=ss,sora[ss]=y,flow[ss]=z,cost[ss]=c,next[ss]=0;
  ss++,next[tail[y]]=ss,tail[y]=ss,sora[ss]=x,flow[ss]=0,cost[ss]=-c,next[ss]=0;
  pow[ss]=ss-1,pow[ss-1]=ss;
}
void link(int x,int y,long long low,long long lim,long long c)
{
  chu[x]+=low,ru[y]+=low;ans+=low*c;
  link2(x,y,lim-low,c);
}
void init()
{
  int i;
  long long x,c;
  scanf("%d%I64d
",&n,&c);ans=0;
  origin();
  for (i=1;i<=n;i++) scanf("%I64d",&h[i]);
  for (i=1;i<=n-1;i++) {
    x=h[i]-h[i+1];
    //    if (x<-c) link(s,i,-c-x,c-x,1);else if (x>c) link(i,t,x-c,x+c,0);
    if (x<-c) link(i,t,-c-x,c-x,0);else if (x>c) link(s,i,x-c,x+c,0);
    else link(s,i,0,x+c,0),link(i,t,0,c-x,0);
  }
  for (i=1;i<=n-2;i++) link(i,i+1,0,oo,1),link(i+1,i,0,oo,1);
  link(t,s,0,oo,0);
  for (i=1;i<=t;i++)
    if (ru[i]>chu[i]) link2(s1,i,ru[i]-chu[i],0);
    else if (ru[i]<chu[i]) link2(i,t1,chu[i]-ru[i],0);
  for (phi=0;spfa(s1,t1);) 
    for (;time++, dfs(s1,oo) ;) ;
  for (i=s1;next[i]!=0;) {
    i=next[i];
    if (flow[i]) {printf("impossible
");return ;}
  }
  printf("%I64d
",ans);
}
int main()
{
  freopen("road.in","r",stdin);
  freopen("road.out","w",stdout);
   int t;
   scanf("%d
",&t);
   for (;t;t--) init();
  return 0;
}

2010年にウトロ郷を建設する難題がある.
難題のデータ&テーマを求めます
—
特殊な点と一般的な点があります
—
各エッジの端点の少なくとも1つの特殊な点は、
—
各ポイントの権限値
L
を選択します.
c*|ΔL[
i
]|,
—
エッジ
(
i
,j
)
対価を計算するには
e*|L[
i
]-L[j]|,
—
求める
min{c*Σ|ΔL[
i
]|+e*Σ|L[
i
]-L[j
]|},
—
L
のみ
1~20
の整数
この問題の場合、前の問題の調整思想に沿っていると思いますが、中間状態が複雑すぎて考えられず(本当に弱い)、特殊点がつながっていない場合を考えると、いずれかの特殊点がある値を取る費用は確かですが、2つの特殊点がつながっていると、1つの点のLを変えると互いに新しい費用が発生し、中間関係を無視して,i番目の点Lをb[i,j]でjとして表し,図b[i,j]からb[i,j+1]への重みをcost[i,j](特殊点の費用を考慮しない)とし,特殊点,b[u,j]からb[v,j]への重みをeの辺とすると仮定すると,最小割開の場合,必ずuとvのL値の差がある層中間の点の重みe辺が割開され,費用案に対応する.したがって、最小割合は求められる.
主な考え方は,中間状態の変化を考慮せずに最終状態を直接決定する費用(少し運動エネルギーの定理に似ている)であるべきである.