UVA 10806 最小费用最大流

终于可以写这道题的题解了,昨天下午纠结我一下下午,晚上才照着人家的题解敲出来,今天上午又干坐着想了两个小时,才弄明白这个问题。

题意很简单,给出一个无向图,要求从1 到 n最短路两次,但是两次不允许经过同一条边(正反都不能经过),如果能成功,则输出两次的最小长度。否则输出一句话。

我当时就马上敲了一个最短路,执行两次,在第一次执行完之后就把所经过的路径的正反都锁定好,不允许下次再访问。。。这样做通过了sample,但是WA了,我后来上网查,原来好多人是我这种做法,。。而且原来这是最小费用最大流问题。

分析一下为什么我的做法不行,因为这道题目要求在能通过的前提下,最短,也就是说,我连续两次最短路,如果第二次不能通过,就放弃,这明显是错的,最终的结果,也许是一条最短路+一条长路,或者两条都不是最短路。。。

所以一种可行的修改方案是,在原来的代码基础上,不是直接*正反两条路,而是*正向,把反向边=权值的相反数,为什么这样的,简而言之,就是给出反悔的机会

我们来思考这样一种实际的例子 如果 path1:起点-p1-A-B-p2-终点; path2:起点-p3-B-A-P4-终点;p1 p2 p3 p4都是互不干扰的路径,这样的话,其实两条路径就是p1-p3

p2-p4,A-B作为公共边,在程序里面最短路确实是这样通过的,但实际上由于权值取反,正好抵消,使得A-B B-A实际意义上是没有被经过,但是路径是通的,这样就能够智能的去选择路径方案。

 

最终我是用最小费用最大流来解决的,通过这个题目,我对最大流有了更深刻的理解,明白了残量图的更大的作用,为什么当时E-K算法里面,找到增广路后需要对正向流进行扩展,同时又对反向流减少,这其实就是对应了现实的流的概念,我递增正向,但是流是守恒的,我可以通过反向把流又送回来,因此用这个方法,使得最大流不会放过任何一个能走通的路径,在E-K算法里,其实流经过了多次往返,只有确定无法走通,才会放弃。。。同时在建图的时候,因为是无向图,所以每条边,都要建立一个相应的负费用边。。。这样的话每个端点实际上连了两条边,一个是自己的正费用边,一个是对面端点的负费用边,我一开始会觉得这样在最短路过程中会不会发生混乱,即这个点往下走,到底是走的自己本身的正费用边,还是负费用边,后来不管费用如何,最短路最终会选择最优的那条,因此不会有问题

因为涉及边数多,所以只能有邻接链表,以及spfa来做。

UVA 10806 最小费用最大流
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct node
{
    int u,v,w,flow,cab,nt;
} e[50000];;8 
int ft[110],d[110],inq[110],p[110];
int cnt,n,m;
int cc,ff;
void add(int u,int v,int cost,int cab)
{
    e[cnt].u=u;   //对每个点添加一条正费用边,以及下面的负费用边
    e[cnt].v=v;
    e[cnt].w=cost;
    e[cnt].cab=cab;
    e[cnt].flow=0;
    e[cnt].nt=ft[u];
    ft[u]=cnt++;

    e[cnt].u=v;
    e[cnt].v=u;
    e[cnt].w=-cost;
    e[cnt].cab=0;
    e[cnt].flow=0;
    e[cnt].nt=ft[v];
    ft[v]=cnt++;
}
void ek()
{
    queue<int> q;
    cc=ff=0;
    int i,j;
    for (;;)
    {
        for (i=0;i<=n+1;i++)
            d[i]=1<<30;
        d[0]=0;
        memset(inq,0,sizeof inq);
        memset(p,-1,sizeof p);
        q.push(0);
        while (!q.empty()) //SPFA搜最短路
        {
            int u=q.front();
            q.pop();
            inq[u]=0;
            for (j=ft[u];j>=0;j=e[j].nt)
            {
                int nx=e[j].v;
                if (e[j].cab>e[j].flow && d[nx]>d[u]+e[j].w)
                {
                    d[nx]=d[u]+e[j].w;
                    p[nx]=j;  //这里不能记录前端点,因为端点指向的边不止一点,因此只能记录该点对应的是哪条边
                    if (!inq[nx])
                    {
                        q.push(nx);
                        inq[nx]=1;
                    }
                }
            }
        }
        if (d[n+1]>=(1<<30)) break;
        int a=1<<30;
        for (i=p[n+1];i>=0;i=p[e[i].u])
        {
            if (a>e[i].cab-e[i].flow)
                a=e[i].cab-e[i].flow;
        }
        for (i=p[n+1];i>=0;i=p[e[i].u])
        {
            e[i].flow+=a;
            e[i^1].flow-=a;//用异或可以使得当前i很快找到对应的那条负费用边 或者 正费用边,因为添加边的时候都是两条两条的加。
        }
        cc+=d[n+1]*a;
        ff+=a;
    }
}
int main()
{
    int i,j;
    while (scanf("%d",&n))
    {
        if (n==0) break;
        cnt=0;
        scanf("%d",&m);
        int a,b,c;
        memset(ft,-1,sizeof ft);
        for (i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c,1);
            add(b,a,c,1);
        }
        add(0,1,0,2); //添加超级原点和终点,这样就方便最后的答案计算。
        add(n,n+1,0,2);
        ek();
        if (ff>=2)
            printf("%d\n",cc);
        else
            puts("Back to jail");
    }
    return 0;
}
UVA 10806 最小费用最大流

UVA 10806 最小费用最大流

上一篇:一:搭建一个最简单的列子


下一篇:IE9 line-height字体垂直居中 失效的解决方法