标签存档：图论

【题目大意】
求一最小费用流，边的费用是a*flow^2。
每条边的容量<=5
【算法分析】
早在我初三的时候，刚刚学习完KM算法，老师给我们做得一套模拟题里就有这个模型。。。是什么工作分配的。当时还很菜很菜，然后居然很奇葩地想到拆点然后套KM，就过了，然后和我一起学的童鞋们都毫无想法，那时兴奋了我一整天=_=。
具体思路如下：
(x+1)^2-x^2=2x+1…
就是每次加2x+1，就能使和依次为每一个完全平方数。
然后2x+1又是递增的。
那么对每一格容量拆成容量为1，费用为2x+1的边，做最小费用流就可以了。
【其他】1Y。
【CODE】
http://xiudaima.appspot.com/code/detail/1684003

【题目大意】
1是源点，其它的n-1个点都可以流出。每滴水所得的费用w[i]。
然后给出一些无向边，流走过这些边，每滴水要消耗费用，并且只能有c滴水通过这条路。
就是比如给定(x,y)，容量为c。
从x到y流过f1滴水，从y到x流过f2滴水，那么f1+f2<=c。
求怎样得到最大利润。
【算法分析】
把那n-1个点汇到一个超级汇中作最大费用最大流就行了。
至于无向边的问题，我们只要加两条有向边就行了。
大牛可以无视下面这个入门问题。。。= =
那么我们现在看一下为啥加两条有向边是对的。
假设一条无向边(x,y)，他允许通过流量为c。
我们现在搞成两个有向边。
1、x->y，容量为c
2、y->x，容量为c
我们再假设最终完成一个流以后，x->y的流为f1，y->x的流为f2，由于对称，不妨设f1>=f2。
那么本质可以变成x->y的流为f1-f2，y->x的流为0。
我们这样考虑：
本来有f2的流S->y->x->T。
同时有f1的流S->x->y->T，并有f1>=f2。
那么现在S->y上的流有f2这么多被分到y->x上了，我们现在把他扯回来。存在y结点上。
于是y点存的水e(y)=f2
再把S->x->y的流扯回来，存在x结点上。
于是x点存的水e(x)=f1
然后现在观察发现。
x->T部分和原来相比，缺了f2，需要补充f2的流来满足流量守恒。
y->T部分和原来相比，缺了f1，需要补充f1的流。
然后我们把e(x)中f1的流分配给x->T这条路，那么分完以后e(x)=f1-f2。
然后再把e(y)中f2的流分配给y->T这条路，那么分完以后e(y)=0。并且y->T这条路还缺少f1-f2的流补充。
于是最后，把e(x)中的流，通过x->y，补给到y->T这条路上。
就完成了这个转化。
所以，凡是x->y中有流，且y->x中也有流的结果，我们都可以转化为只有一条有流的结果。
并且边上的流都小于等于原来的。
这样，就证明了这样加边最后必然与合法解所对应，如果要输出方案的话，把所有这种对应边的流量相互抵消以后输出，就可以得到满足条件的解。
/
/
/
/
/
但是，我们只是证明了无费用的情况。
如果按照这样转化总费用是会变化的！
对于(x,y)这条边而言，一开始取了f1+f2个单位的费用，而转化以后只取了f1-f2的费用。
我们现在再分情况仔细YY一下：
1、求最大费用流，如果该无向边权值>0，显然无法求。。。就像有正权环的最长路一样。
但是如果该无向边的权值<0，显然按照上面的推导，f1+f2>f1-f2。（假设f1>=f2 && f1,f2>0）。
我们的费用流不会这么笨去取那个更差的解。
2、求最小费用流，基本上面的词取反义词就是了T_T。

还有，本题求的是最大费用流，流不一定要最大，只要流满足限制即可。我们找增广路如果找到增广费用小于等于0，就可以马上停止了。
如果是最大费用最大流，找增广路的话，要找到找不到为止。
【其它】1Y。呃~希望有同样困惑的童鞋们看完可以清楚一点。
【CODE】
#include #include #include #include #include using namespace std;
const int N=105;
const int E=40000;
const int INF=0x7FFFFFFF;
struct edge{int x,y,c,w;edge *next,*op;}g[E],*ls[N],*fa[N];
int m,n,S,T,e,cost;
int d[N],v[N],L[N];

void addedge(int x,int y,int c,int w){
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].w= w; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
}

void init(){
for (int i=1;i<=n+1;i++) ls[i]=NULL;
e=-1; S=1; T=n+1;
for (int w,i=2;i<=n;i++){
cin >> w;
addedge(i,T,INF,w);
}
for (int x,y,c,w,i=1;i<=m;i++){
cin >> x >> y >> c >> w;
addedge(x,y,c,-w);
addedge(y,x,c,-w);
}
}

bool spfa(){
for (int i=S;i<=T;i++){
d[i]=-INF;
v[i]=0;
}
d[S]=0; v[S]=1; L[1]=S;
int head=0,tail=1;
while (head!=tail){
head=(head+1)%N;
for (edge *t=ls[L[head]];t;t=t->next)
if (t->c && d[t->x]+t->w>d[t->y]){
d[t->y]=d[t->x]+t->w;
fa[t->y]=t;
if (!v[t->y]){
v[t->y]=1;
L[tail=(tail+1)%N]=t->y;
}
}
v[L[head]]=0;
}
return d[T]>0;
}

void change(){
int nf=INF;
for (int i=T;i!=S;i=fa[i]->x)
nf=min(nf,fa[i]->c);
cost+=nf*d[T];
for (int i=T;i!=S;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
}

void MCMF(){
cost=0;
while (spfa()) change();
cout << cost << 'n';
}

int main(){
ios::sync_with_stdio(false);
while (cin >> n >> m){
init();
MCMF();
}
}

【题目大意】
给定源汇，一些弧必须满载。问源到汇的最小流是多少？
【算法分析】
通过加弧当然。。。这是最简单的方法。。。反向增广这么高科技的就算了。。。
【其它】
复习上下界网络流。居然没1Y。原因1是有一个地方N写成E了。（就是数组没开够。。。），原因2是MLE。
我的习惯一直是把数组开大很多的。。。SGU这种限这么死的地方就果断悲剧。
【CODE】
#include #include #include const int N=155;
const int E=N*N*6;
struct edge{int x,y,c,next;};

struct Network_t{
    int e,S,T,Flow;
    edge g[E];
    int ls[N],fa[N],cur[N],num[N],d[N];
    void init(){
        e=1;
        memset(ls,0,sizeof(ls));
    }

    void clr(){
        for (int i=3;i<=e;i+=2){
            g[i-1].c+=g[i].c;
            g[i].c=0;
        }
    }

    void addedge(int x,int y,int c){
        g[++e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=e;
        g[++e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=e;
    }

    void relabel(int k){
        cur[k]=ls[k];
        int mm=T;
        for (int t=ls[k];t;t=g[t].next)
          if (g[t].c && d[g[t].y]            mm=d[g[t].y];
        d[k]=mm+1;
    }

    void change(){
        int nf=0x7FFFFFFF;
        for (int i=T;i!=S;i=g[fa[i]].x)
          if (g[fa[i]].c        for (int i=T;i!=S;i=g[fa[i]].x){
            g[fa[i]].c-=nf;
            g[fa[i]^1].c+=nf;
        }
        Flow+=nf;
    }

    void sap(){
        Flow=0;
        int i;
        for (i=1;i<=T;i++){
            d[i]=num[i]=0;
            cur[i]=ls[i];
        }
        i=S;
        while (d[S]            int &t=cur[i];
            for (;t;t=g[t].next)
              if (g[t].c && d[g[t].y]+1==d[g[t].x]) break;
            if (t){
                fa[g[t].y]=t;
                i=g[t].y;
                if (i==T){
                    change();
                    i=S;
                }
            }
            else{
                if (!–num[d[i]]) break;
                relabel(i);
                ++num[d[i]];
                if (i!=S) i=g[fa[i]].x;
            }
        }
    }
}Network;

int n,m,SF;
int din[N],dout[N],Type[E],C[E];

void init(){
    Network.init();
    scanf("%d%d",&n,&m);
    SF=0;
    for (int x,y,c,t,i=1;i<=m;i++){
      scanf("%d%d%d%d",&x,&y,&c,&t);
      if (t){
          din[y]+=c;
          dout[x]+=c;
          SF+=c;
      }
      else Network.addedge(x,y,c);
      Type[i]=t;
      C[i]=c;
    }
}

void build(){
    Network.S=n+1; Network.T=n+2;
    int i;
    for (i=1;i<=n;i++){
        if (din[i]) Network.addedge(n+1,i,din[i]);
        if (dout[i]) Network.addedge(i,n+2,dout[i]);
    }
    Network.addedge(n,1,0x7FFFFFFF);
}

void output(){
    int cnt=1;
    for (int i=1;i<=m;i++){
      if (Type[i]) printf("%d",C[i]);
      else printf("%d",Network.g[cnt+=2].c);
      if (i==m) puts("");
           else putchar(‘ ’);
    }
}

void solve(){
    Network.sap();
    if (Network.Flow!=SF){
        puts("Impossible");
        return;
    }
    int l,r,mid;
    l=0; r=Network.g[Network.e].c;
    while (l        mid=(l+r)/2;
        Network.clr();
        Network.g[Network.e-1].c=mid;
        Network.sap();
        if (Network.Flow==SF) r=mid;
                         else l=mid+1;
    }
    Network.clr();
    Network.g[Network.e-1].c=l;
    Network.sap();
    printf("%dn",l);
    output();
}

int main(){
    init();
    build();
    solve();
    return 0;
}

【题目大意】有n栋楼和一个SuperMan，每个都拥有一个唯一的高度，然后SuperMan每次会从第i高的楼，跳到第i+1高的楼上去。这些楼被安排在一个一维坐标轴上，然后这些楼有一个初始顺序，你是不能改变的。这些楼必须在整点上，并且不允许重叠，然后你要帮SuperMan安排这些楼，使得最高的楼和最低的楼距离之差最大。如果没有可行解，输出-1.

【算法分析】差分约束典型题目。根据那两个条件建好边，以最低楼和最高楼中顺序靠前的做起点，搞单源最短路，有环判无解，否则输出最高楼和最低楼d值之差的绝对值即可。

【其它】1Y

【CODE】

#include const int N=1005;
const int E=500005;
const int INF=0x7FFFFFFF/2-22;
int n,e,D;
int d[N],a[N],zz[N];
struct edge{int x,y,w;}g[E];

int cmp(const void *A,const void *B){
    return a[*((int*)A)]-a[*((int*)B)];
}

void add(int x,int y,int w){
     g[++e].x=x; g[e].y=y; g[e].w=w;
}

void init(){
     int i;
     scanf("%d%d",&n,&D);
     for (i=1;i<=n;i++){
       scanf("%d",&a[i]); zz[i]=i; } qsort(zz+1,n,sizeof(int),cmp);
     e=0;
     for (i=1;i     for (i=1;i       if (zz[i]                     else add(zz[i+1],zz[i],D);
}

void Bellman_Ford(){
     int i,j;
     for (i=1;i<=n;i++) d[i]=INF;
     if (zz[1]                 else d[zz[n]]=0;
     bool flag;
     for (i=1;i<=n;i++){
         flag=false;
         for (j=1;j<=e;j++)
           if (d[g[j].x]+g[j].w             flag=true;
             d[g[j].y]=d[g[j].x]+g[j].w;
           }
         if (!flag) break;
     }
     if (flag) { puts("-1"); return; }
     else if (zz[1]                      else printf("%dn",d[zz[1]]-d[zz[n]]);
}

int main(){
    int i,Tc;
    scanf("%d",&Tc);
    for (i=1;i<=Tc;i++){
        printf("Case %d: ",i);
        e=0;
        init();
        Bellman_Ford();
    }
    return 0;
}

【题目大意】

给出N个点，M条带权无向边。

让你选一些边，使得能用多个圈把图上所有点精确覆盖。输出所有圈的长度之和。

如果不存在这样的圈，输出-1.

【算法分析】

这个是经典题。。。

如果整个图是一个哈密顿回路的话，那么每个点的度都为2。

那么我们把每个点拆开。并给哈密顿圈定义一个方向。

那么一个负责出度，一个负责入度。最佳匹配即可。

【其它】1Y

【CODE】

#include const int N=20005;
const int E=200005;
const int INF=1000000000;
int n,m,e,S,T,cost,Flow;
int v[N],d[N],L[N];
struct edge{int x,y,c,w;edge *next,*op;}g[E],*ls[N],*fa[N];

void addedge(int x,int y,int c,int w){
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].w= w; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
}

void init(){
e=0;
memset(ls,0,sizeof(ls));
int i,x,y,w;
scanf("%d%d",&n,&m);
S=0; T=n+m+1;
for (i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&w);
addedge(x,y+n,1,w);
addedge(y,x+n,1,w);
}
for (i=1;i<=n;i++){
addedge(n+i,T,1,0);
addedge(S,i,1,0);
}
}

bool spfa(){
int i,head=0,tail=1;
for (i=S;i<=T;i++){
d[i]=INF;
v[i]=0;
}
d[S]=0; v[S]=1; L[1]=S;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=ls[L[head]];t;t=t->next)
if (t->c && d[t->x]+t->wd[t->y]=d[t->x]+t->w;
fa[t->y]=t;
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
L[tail]=t->y;
}
}
v[L[head]]=0;
}
return d[T]!=INF;
}

void change(){
cost+=d[T];
for (int i=T;i!=S;i=fa[i]->x){
fa[i]->c–;
fa[i]->op->c++;
}
Flow++;
}

void MCMF(){
cost=Flow=0;
while (spfa()) change();
if (Flow!=n) puts("NO");
else printf("%dn",cost,Flow);
}

int main(){
int Tc,i;
scanf("%d",&Tc);
for (i=1;i<=Tc;i++){
printf("Case %d: ",i);
init();
MCMF();       
}
}