icontofig | 发布于 2019-07-23 13:56:02 | 阅读量 435 | 最短路 网络流 最小割
发布于 2019-07-23 13:56:02 | 最短路 网络流 最小割

题目大意

给出一张图,让你删除一些边,使得从1到n的最短路变大,代价为删除边的长度。若本身1与n不连通则输出0。

题解

有人说dinic 会T炸,那应该是他们dinic板子不够优。

这题其实就是先求出1——n的所有最短路,以所有最短路为边建一张图,然后割掉一些边使得1与n不连通。

这是很明显的最小割模型……我们最小割的原图中的所有边的流量即为其原先的长度。

至于如何求所有最短路。

直接求出从1出发的单源最短路,然后遍历一遍所有边,检查当前的边是否是最短路上的边即可。

我寻思我用复杂度比较玄学的SPFA+dinic也过去了啊……而且是1A那种,怎么那么多人说会T炸呢?

代码

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e4+5;
int T;
typedef long long ll;
const ll INF = 1e15;
struct Flow{
    struct edge{
        int to,next;
        ll cap;
    }e[maxn<<2];
    int h[maxn];
    int cur[maxn];
    int cnt;
    void init(){
        cnt = 0;
        memset(h,-1,sizeof(h));
        return;
    }
    void add(int u,int v,ll c){
        e[cnt].to = v;e[cnt].cap = c;e[cnt].next = h[u];h[u] = cnt++;
        e[cnt].to = u;e[cnt].cap = 0;e[cnt].next = h[v];h[v] = cnt++;
        return;
    }
    ll d[maxn];
    bool BFS(int s,int t){
        queue<int>q;
        for(int i = s;i <= t;++i){
            d[i] = INF;
        }
        q.push(s);
        d[s] = 0;
        while(!q.empty()){
            int x = q.front();
            q.pop();
            for(int i = h[x];i != -1;i = e[i].next){
                int v = e[i].to;
                if(d[v] == INF && e[i].cap > 0){
                    d[v] = d[x] + 1;
                    q.push(v);
                }
            }
        }
        return d[t] != INF;
    }
    ll DFS(int now,int t,ll a){
        if(a == 0 || now == t)return a;
        ll flow = 0,f;
        for(int &i = cur[now];i != -1;i = e[i].next){
            int v = e[i].to;
            if(d[v] == d[now]+1 && e[i].cap > 0){
                f = min(a - flow,e[i].cap);
                f = DFS(v,t,f);
                flow += f;
                e[i].cap -= f;
                e[i^1].cap += f;
                if(flow == a)return flow;
            }
        }
        return flow;
    }
    ll dinic(int s,int t){
        ll flow = 0;
        while(BFS(s,t)){
            for(int i = s;i <= t;++i)cur[i] = h[i];
            flow += DFS(s,t,INF);
        }
        return flow;
    }
}ans;
struct edge2{
    int to,next;
    ll dis;
}ed[maxn<<1];
int g[maxn];
int cnt = 0;
void add2(int u,int v,ll d){
    ed[cnt].to = v;ed[cnt].dis = d;ed[cnt].next = g[u];g[u] = cnt++;
    return;
}
ll dis[maxn];
int vis[maxn];
void SPFA(int s,int t){
    for(int i = s;i <= t;++i){
        dis[i] = INF;
        vis[i] = 0;
    }
    queue<int>q;
    dis[s] = 0;
    q.push(s);
    vis[s] = 1;
    while(!q.empty()){
        int now = q.front();
        q.pop();
        vis[now] = 0;
        for(int i = g[now];i != -1;i = ed[i].next){
            int v = ed[i].to;
            if(dis[v] > dis[now] + ed[i].dis){
                dis[v] = dis[now] + ed[i].dis;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return;
}
void BF(int x){
    for(int i = g[x];i != -1;i = ed[i].next){
        int v = ed[i].to;
        if(dis[v] == dis[x] + ed[i].dis){
            ans.add(x,v,ed[i].dis);
        }
    }
    return;
}
int n,m;
int u,v,c;
int main(){
    T = get_num();
    while(T--){
        n = get_num();
        m = get_num();
        ans.init();
        memset(g,-1,sizeof(g));
        cnt = 0;
        for(int i = 1;i <= m;++i){
            u = get_num();
            v = get_num();
            c = get_num();
            add2(u,v,c);
        }
        SPFA(1,n);
        for(int i = 1;i < n;++i)
            BF(i);
        ll sum = ans.dinic(1,n);
        printf("%lld\n",sum);
    }
    return 0;
}



内容更新于: 2019-07-23 13:56:03
链接地址: http://blog.leanote.com/post/icontofig/66748b19a106

上一篇: 2019 Multi-University Training Contest 1 1002 Operation 线性基

下一篇: 2019 Multi-University Training Contest 1 1004 Vacation

435 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航