hdu 6582（最短路+最小割）

分手后的思念是犯贱 2021-11-05 13:18 233阅读 0赞

[传送门][Link 1]

# 题意： #

给你一张有向图，现在你需要删除一些边，每次删除的花费是边的权值，使得最短路增大，现在问你最小的花费。

# 题解： #

如果要使得最短路增大，显然是删掉最短路上的一些边。我们发现，原图的最短路也能够形成一张\\(\\text\{DAG\}\\)，如果我们要使得最短路增大，等价于要求一个最小的花费，使得我们可以破坏这个\\(\\text\{DAG\}\\)，而显然这个东西就是最小割。因此我们只需要把原图的最短路建边，之后在新的图上跑最小割即可。至于在原图最短路上建边，我们只需要对以\\(1\\)号结点以及\\(n\\)号结点分别求最短路，之后对于每一条边所连接的两个结点\\(u\\)和\\(v\\)，如果\\(dis\_\{1u\}+dis\_\{nv\}+val\_\{uv\}=dis\_\{1n\}\\)则证明该条边是最短路上的边。

看了下数据，看起来好像不太强大啊，为了不T，在这样的数据量下最好还是得用优秀的最大流算法……

# 代码： #

#include <bits/stdc++.h>
    #define maxn 30005
    using namespace std;
    typedef long long ll;
    const ll INF=0x3f3f3f3f3f3f3f3f;
    int head1[maxn],cnt1;
    int head2[maxn],cnt2;
    
    int n,m;
    struct edge{
        int to,next,from;
        long long cost;
    }q1[maxn],q2[maxn];
    void add_edge(int from,int to,int cost,int *head,int &cnt,edge *q){
        q[cnt].to=to;
        q[cnt].from=from;
        q[cnt].cost=cost;
        q[cnt].next=head[from];
        head[from]=cnt++;
    }
    typedef pair<int,ll>P;
    ll d1[maxn],d2[maxn],e[maxn],h[maxn],cnth[maxn];
    void diji(int s,int *head,edge *q,ll *d){
        for(int i=1;i<=n;i++) d[i]=INF;
        priority_queue<P,vector<P>,greater<P> >que;
        d[s]=0;
        que.push(P(0,s));
        while(!que.empty()){
            P p=que.top();
            que.pop();
            int x=p.second;
            if(d[x]<p.first) continue;
            for(int i=head[x];i!=-1;i=q[i].next){
                edge id=q[i];
                if(d[id.to]>d[x]+id.cost){
                    d[id.to]=d[x]+id.cost;
                    que.push((P(d[id.to],id.to)));
                }
            }
        }
    }
    //hlpp求解最大流
    int head3[maxn],cntt=2;
    struct Node{
        int to,next;
        ll val;
    }qq[maxn<<1];
    int vis[maxn];
    int sp,ep;
    struct cmp{
        inline bool operator()(int a,int b) const{
            return h[a]<h[b];
        }
    };
    void addedge(int from,int to,int val){
        qq[cntt].to=to;
        qq[cntt].val=val;
        qq[cntt].next=head3[from];
        head3[from]=cntt++;
    }
    void add_edge2(int from,int to,int val){
        addedge(from,to,val);
        addedge(to,from,0);
    }
    void bfs(){
        memset(h,0x3f,sizeof(h));
        h[ep]=0;
        queue<int>que;
        que.push(ep);
        while(!que.empty()){
            int x=que.front();
            que.pop();
            vis[x]=0;
            for(int i=head3[x];i!=-1;i=qq[i].next){
                int to=qq[i].to;
                if(qq[i^1].val&&h[to]>h[x]+1){
                    h[to]=h[x]+1;
                    if(vis[to]==0){
                        que.push(to);
                        vis[to]=1;
                    }
                }
            }
        }
        return;
    }
    void init(int *head,int &cnt){
        for(int i=0;i<maxn;i++) head[i]=-1;
        memset(vis,0,sizeof(vis));
        memset(cnth,0,sizeof(cnth));
        memset(e,0,sizeof(e));
        cnt=0;
    }
    priority_queue<int,vector<int>,cmp>Q;
    inline void push_(int x){
        for(int i=head3[x];i!=-1;i=qq[i].next){
            int to=qq[i].to;
            if(qq[i].val&&h[to]+1==h[x]){
                int mi=min(qq[i].val,e[x]);
                qq[i].val-=mi;
                qq[i^1].val+=mi;
                e[x]-=mi;
                e[to]+=mi;
                if(vis[to]==0&&to!=ep&&to!=sp){
                    Q.push(to);
                    vis[to]=1;
                }
                if(e[x]==0)break;
            }
        }
    }
    inline void relabel(int x){
        h[x]=INF;
        for(int i=head3[x];i!=-1;i=qq[i].next){
            int to=qq[i].to;
            if(qq[i].val&&h[to]+1<h[x]){
                h[x]=h[to]+1;
            }
        }
    }
    ll hlpp(){
        register int i;
        bfs();
        if(h[sp]==INF)return 0;
        h[sp]=n;
        for(i=1;i<=n;i++)if(h[i]<INF)cnth[h[i]]++;
        for(i=head3[sp];i!=-1;i=qq[i].next){
            int to=qq[i].to;
            ll mi=qq[i].val;
            if(mi){
                e[sp]-=mi;
                e[to]+=mi;
                qq[i].val-=mi;
                qq[i^1].val+=mi;
                if(to!=ep&&vis[to]==0&&to!=sp){
                    Q.push(to);
                    vis[to]=1;
                }
            }
        }
        while(!Q.empty()){
            int x=Q.top();
            vis[x]=0;
            Q.pop();
            push_(x);
            if(e[x]){
                cnth[h[x]]--;
                if(cnth[h[x]]==0){
                    for(int i=1;i<=n;i++){
                        if(i!=sp&&i!=ep&&h[i]>h[x]&&h[i]<n+1){
                            h[i]=n+1;
                        }
                    }
                }
                relabel(x);
                cnth[h[x]]++;
                Q.push(x);
                vis[x]=1;
            }
        }
        return e[ep];
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--){
            scanf("%d%d",&n,&m);
            init(head1,cnt1);
            init(head2,cnt2);
            init(head3,cntt);
            cntt=2;
            for(int i=1;i<=m;i++){
                int from,to,cost;
                scanf("%d%d%d",&from,&to,&cost);
                add_edge(from,to,cost,head1,cnt1,q1);
                add_edge(to,from,cost,head2,cnt2,q2);
            }
            diji(1,head1,q1,d1);
            diji(n,head2,q2,d2);
            if(d1[n]==INF){
                puts("0");
                continue;
            }
            sp=1,ep=n;
            for(int i=1;i<=n;i++){
                for(int j=head1[i];j!=-1;j=q1[j].next){
                    int to=q1[j].to;
                    int from=q1[j].from;
                    int val=q1[j].cost;
                    if(d1[from]+d2[to]==d1[n]-val){
                        add_edge2(from,to,val);
                    }
                }
            }
            printf("%lld\n",hlpp());
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Chen-Jr/p/11228767.html

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6582