hdu-携程复赛-最短路径的代价-抠图+最小割

被数据范围坑死了。。。

说好的m<=10000,改成了m<=11000....

把所有最短路涉及到的边抠出来。

然后建图，边的权值为边的c。

然后对图求一个最小割。

最小割割掉的所有的边即为要选调的边。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include<queue>
using namespace std;
#define INF 99999999
const int maxn =1110;
const int maxm =25000;
const int oo = 1<<29;
struct Arclist
{
    int cnt, head[maxn], dis[maxn];
    int cur[maxn], pre[maxn], gap[maxn], aug[maxn];
    struct node
    {
        int u, v, w, next;
    } edge[maxm];
    void init(int n)
    {
        cnt = 0;
        std::fill_n(head, n+1, -1);
    }
    void add(int u, int v, int w)
    {
        edge[cnt].u = u;
        edge[cnt].v = v;
        edge[cnt].w = w;
        edge[cnt].next = head[u];
        head[u] = cnt++;
        edge[cnt].u = v;
        edge[cnt].v = u;
        edge[cnt].w = 0;
        edge[cnt].next = head[v];
        head[v] = cnt++;
    }
    int sap(int s, int e, int n)
    {
        int max_flow = 0, u = s;
        int mindis;
        for(int i = 0; i <= n; i++)
        {
            cur[i] = head[i];
            dis[i] = 0;
            gap[i] = 0;
        }
        aug[s] = oo;
        pre[s] = -1;
        gap[0] = n;
        while(dis[s]<n)
        {
            bool flag = false;
            if(u==e)
            {
                max_flow += aug[e];
                for(int v = pre[e]; v != -1; v = pre[v])
                {
                    int id = cur[v];
                    edge[id].w -= aug[e];
                    edge[id^1].w += aug[e];
                    aug[v] -= aug[e];
                    if(edge[id].w==0) u = v;
                }
            }
            for(int id = cur[u]; id != -1; id = edge[id].next)
            {
                int v = edge[id].v;
                if(edge[id].w>0 && dis[u]==dis[v]+1)
                {
                    flag = true;
                    pre[v] = u;
                    cur[u] = id;
                    aug[v] = std::min(aug[u], edge[id].w);
                    u = v;
                    break;
                }
            }
            if(flag==false)
            {
                if(--gap[dis[u]]==0) break;
                mindis = n;
                cur[u] = head[u];
                for(int id = head[u]; id != -1; id = edge[id].next)
                {
                    int v = edge[id].v;
                    if(edge[id].w>0 && dis[v]<mindis)
                    {
                        mindis = dis[v];
                        cur[u] = id;
                    }
                }
                dis[u] = mindis+1;
                ++gap[dis[u]];
                if(u!=s) u = pre[u];
            }
        }
        return max_flow;
    }
} G;
struct gra
{
    struct list
    {
        int u,v,w,c,next;
    } edge[maxm];
    int head[maxn];
    int nums;
    void init()
    {
        nums=0;
        memset(head,-1,sizeof(head));
    }
    void add(int u,int v,int w,int c)
    {
        edge[nums].u=u;edge[nums].v=v;
        edge[nums].c=c;edge[nums].w=w;
        edge[nums].next=head[u];head[u]=nums++;
    }
}gs;
int dij(int st,int ed,int n)
{
    int i;
    int dis[maxn];
    int vis[maxn];
    for(i=1;i<=n;i++)
    {
        dis[i]=INF;
        vis[i]=0;
    }
    dis[st]=0;
    while(1)
    {
        int minn=INF;
        int x;
        for(i=1;i<=n;i++)
        {
            if(vis[i])continue;
            if(minn>dis[i])
            {
                minn=dis[i];
                x=i;
            }
        }
        if(minn==INF)break;
        vis[x]=1;
        for(i=gs.head[x];i!=-1;i=gs.edge[i].next)
        {
            int v=gs.edge[i].v;
            int w=gs.edge[i].w;
            if(vis[v])continue;
            if(dis[v]>dis[x]+w)dis[v]=dis[x]+w;
        }
    }
    //for(i=1;i<=n;i++)cout<<dis[i]<<" ";
   // cout<<endl;
    queue<int>que;
    while(!que.empty())que.pop();
    que.push(ed);
    memset(vis,0,sizeof(vis));
    vis[ed]=1;
    while(!que.empty())
    {
        int x=que.front();
        que.pop();
        if(x==st)continue;
        for(i=gs.head[x];i!=-1;i=gs.edge[i].next)
        {
            int u=gs.edge[i].v;
            int w=gs.edge[i].w;
            int c=gs.edge[i].c;
            if(dis[u]+w==dis[x])
            {
              //  cout<<u<<"-"<<x<<":"<<c<<endl;
                G.add(u,x,c);
                if(!vis[u])que.push(u);
                vis[u]=1;
            }
        }
    }
    return G.sap(st,ed,n);
}
int main()
{
    int n,m,st,ed,a,b,w,c;
    while(~scanf("%d%d",&n,&m)&&(n||m))
    {
        gs.init();
        scanf("%d%d",&st,&ed);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d%d",&a,&b,&w,&c);
            gs.add(a,b,w,c);
            gs.add(b,a,w,c);
        }
        G.init(maxn-1);
        cout<<dij(st,ed,n)<<endl;
    }
    return 0;
}

hdu-携程复赛-最短路径的代价-抠图+最小割,布布扣,bubuko.com

hdu-携程复赛-最短路径的代价-抠图+最小割

原文：http://blog.csdn.net/rowanhaoa/article/details/23705391