HDU 6582 Path——————2019多校第一场，最短路+最大流

亦凉 2021-11-26 08:02 289阅读 0赞

# [Path][] #

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)  
Total Submission(s): 1831 Accepted Submission(s): 496

**Problem Description**  
Years later, Jerry fell in love with a girl, and he often walks for a long time to pay visits to her. But, because he spends too much time with his girlfriend, Tom feels neglected and wants to prevent him from visiting her.  
After doing some research on the neighbourhood, Tom found that the neighbourhood consists of exactly n houses, and some of them are connected with directed road. To visit his girlfriend, Jerry needs to start from his house indexed 1 and go along the shortest path to hers, indexed n.  
Now Tom wants to block some of the roads so that Jerry has to walk longer to reach his girl’s home, and he found that the cost of blocking a road equals to its length. Now he wants to know the minimum total cost to make Jerry walk longer.  
Note, if Jerry can’t reach his girl’s house in the very beginning, the answer is obviously zero. And you don’t need to guarantee that there still exists a way from Jerry’s house to his girl’s after blocking some edges.

**Input**  
The input begins with a line containing one integer T(1≤T≤10), the number of test cases.  
Each test case starts with a line containing two numbers n,m(1≤n,m≤10000), the number of houses and the number of one-way roads in the neighbourhood.  
m lines follow, each of which consists of three integers x,y,c(1≤x,y≤n,1≤c≤109), denoting that there exists a one-way road from the house indexed x to y of length c.

**Output**  
Print T lines, each line containing a integer, the answer.

**Sample Input**  
1  
3 4  
1 2 1  
2 3 1  
1 3 2  
1 3 3

**Sample Output**  
3

--------------------

两遍 d i j k s t r a dijkstra dijkstra算法建一个最短路的图，然后求一下最大流

链式前向星存图

//#include<bits/stdc++.h>
    #include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<map>
    #include<bitset>
    #include<set>
    #include<vector>
    
    
    using namespace std;
    typedef long long ll;
    typedef pair<int ,int> P;
    
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 2e4+7;
    int t,n,m;
    
    struct Edge{
        
            int nxt, to;
            ll w;
    }e[10010], f[10010];
    int cnt = 1, head[MAXN], fcnt = 1,fhead[MAXN];
    
    void add(int u, int v, int w){
        //建立图和反向图
            e[cnt] = {
        head[u], v, w};
            head[u] = cnt++;
            f[fcnt] = {
        fhead[v], u,w};
            fhead[v] = fcnt++;
    }
    
    ll dis[MAXN], fdis[MAXN];
    bool vis[MAXN];
    
    struct DijkHeap{
        
            int u;
            ll d;
            bool operator < (const DijkHeap &a)const{
        
                    return d > a.d;
            }
    }dijktemp;
    
    void dijkstra(){
        
            // cout<<"********"<<endl;
            priority_queue<DijkHeap> q;
            memset(dis, 0x7f, sizeof(ll)*(n+2));
            memset(vis, 0, sizeof(bool)*(n+2));
            dis[1] = 0;
            q.push({
        1,0});
            while(!q.empty()){
        
                    dijktemp = q.top(); q.pop();
                    int u = dijktemp.u;
                    ll d  = dijktemp.d;
                    vis[u] = 1;
                    for(int i=head[u]; i; i=e[i].nxt){
        
                            int v = e[i].to;
                            if(vis[v])      continue;
                            if(dis[v]>d+e[i].w){
        
                                    dis[v] = d+e[i].w;
                                    q.push({
        v,dis[v]});
                            }
                    }
            }
            // for(int i=1;i<=n;++i)
            // cout<<i<<":"<<dis[i]<<endl;
            // cout<<"***"<<n<<endl;
            memset(fdis, 0x7f, sizeof(fdis));
            memset(vis, 0, sizeof(vis));
            fdis[n] = 0;
            q.push({
        n, 0});
            while(!q.empty()){
        
                    dijktemp = q.top(); q.pop();
                    int u = dijktemp.u;
                    ll  d = dijktemp.d;
                    vis[u] = 1;
                    for(int i = fhead[u]; i; i = f[i].nxt){
        
                            int v = f[i].to;
                            if(vis[v])      continue;
                            if(fdis[v] > f[i].w + d){
        
                                    fdis[v] = f[i].w + d;
                                    q.push({
        v, fdis[v]});
                             }
                    }
            }
            // for(int i=1;i<=n;++i)
            //         cout<<i<<":"<<fdis[i]<<endl;
    }
    
    struct WEdge{
        
            int nxt, to;
            ll flow;
    }we[2*MAXN];
    
    int whead[MAXN] = {
        0}, wcnt = 2;
    
    void wadd(int u, int v, long long f){
        
            we[wcnt] = {
        whead[u], v, f};
            whead[u] = wcnt++;
            we[wcnt] = {
        whead[v], u, 0};
            whead[v] = wcnt++;
    }
    
    int dep[MAXN] = {
        0};
    
    bool bfs(){
        
            memset(dep, 0, sizeof(int)*(n+2));
            queue<int>q;
            dep[1] = 1;
            q.push(1);
            while(!q.empty()){
        
                    int u = q.front(); q.pop();
                    for(int i = whead[u]; i; i = we[i].nxt){
        
                            ll v = we[i].to;
                            if(!dep[v] && we[i].flow){
        
                                    dep[v] = dep[u] + 1;//分层图
                                    q.push(v);
                            }
                    }
    
            }
            return dep[n] != 0;
    }
    
    long long dfs(int u, ll fflow){
        
            if(u == n || fflow == 0ll)       return fflow;
            ll sum = 0;
            for(int i = whead[u]; i; i = we[i].nxt){
        
                    int v = we[i].to;
                    if(dep[v] == dep[u] + 1 && we[i].flow){
        
                            ll delta = dfs(v, min(fflow - sum, we[i].flow));
                            sum += delta;
                            we[i].flow -= delta;
                            we[i^1].flow += delta;
                            if(fflow<=sum)  break;
                    }
            }
            if(!sum)        dep[u] = -1;
            return sum;
    }
    
    long long dinic(){
        
            ll ans = 0;
            while(bfs()){
        
                    while(ll temp = dfs(1, 0x3f3f3f3f3f3f3f3f))
                            ans += temp;
            }
            return ans;
    }
    
    void init(){
        
            cnt = fcnt = 1;
            wcnt = 2;
            memset(head, 0, sizeof(int)*(n+2));
            memset(fhead, 0, sizeof(int)*(n+2));
            memset(whead, 0, sizeof(int)*(n+2));
    }
    
    
    int main(){
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            scanf("%d",&t);
            while(t--){
        
                    init();
                    scanf("%d %d",&n,&m);
    
                    for(int i=0;i<m;++i){
        
                            int x,y,z;
                            scanf("%d %d %d",&x,&y,&z);
                            add(x,y,(ll)z);
                    }
                    dijkstra();
                    for(int u=1;u<=n;++u){
        
                            for(int i=head[u]; i; i=e[i].nxt){
        
                                    int v = e[i].to;
                                    if(dis[u] + e[i].w + fdis[v]==dis[n]){
        
                                            wadd(u, v, e[i].w);
                                            // printf("***%d   %d   %lld\n", u, v, e[i].w);
                                    }
                            }
                    }
                    printf("%lld\n",dinic());
            }
    
    
            return 0;
    }

然后，我自个又用vector存的图，根据原来的思路又写了一边  
G是原图  
rG是原图的反图  
wG是最短路构成的图

//#include<bits/stdc++.h>
    #include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<map>
    #include<bitset>
    #include<set>
    #include<vector>
    
    
    using namespace std;
    typedef long long ll;
    typedef pair<ll ,ll> P;
    
    const ll INF  = 0x3f3f3f3f3f3f3f3f;
    const ll MAXN = 2e5+7;
    
    ll n,m,t;
    struct edge{
        
            ll to,cost;
    };
    ll dis[MAXN], rdis[MAXN];
    vector<edge>  G[MAXN];
    vector<edge> rG[MAXN];
    
    ll Min(ll x, ll y)
    {
        
            return x>y?y:x;
    }
    
    void dijkstra(){
        
            priority_queue<P, vector<P>, greater<P> > que;
            que.push(P(0,1));
            memset(dis,0x3f,sizeof(ll)*(n+2));
            dis[1] = 0LL;
            // cout<<dis[1]<<" ";
    
            while(!que.empty()){
        
                    P p = que.top(); que.pop();
                    ll v = p.second;
                    if(dis[v] < p.first)    continue;
                    for(ll i = 0; i < (ll)G[v].size(); ++i){
        
                            edge e = G[v][i];
                            if(dis[e.to] > dis[v] + e.cost){
        
                                    dis[e.to] = dis[v] + e.cost;
                                    que.push(P(dis[e.to], e.to));
    
                            }
                    }
    
            }
            // cout<<dis[1]<<" ";
            // cout<<dis[n]<<endl;
            que.push(P(0,n));
            memset(rdis,0x3f,sizeof(ll)*(n+2));
            rdis[n] = 0LL;
    
            while(!que.empty()){
        
                    P p = que.top(); que.pop();
                    ll v = p.second;
                    if(rdis[v] < p.first)    continue;
                    for(ll i = 0; i < (ll)rG[v].size(); ++i){
        
                            edge e = rG[v][i];
                            if(rdis[e.to] > rdis[v] + e.cost){
        
                                    rdis[e.to] = rdis[v] + e.cost;
                                    que.push(P(rdis[e.to], e.to));
                                    // cout<<e.to<<" "<<dis[e.to]<<endl;
                            }
                    }
            }
            // cout<<rdis[n]<<endl;
    }
    
    struct wedge{
        ll to, cap, rev;};
    
    vector<wedge> wG[MAXN];
    ll level[MAXN];
    ll  iter[MAXN];
    
    void add_edge(ll from, ll to, ll cap){
        
            wG[from].push_back((wedge){
        to, cap, (ll) wG[to].size()});
            wG[to].push_back((wedge){
        from, 0, (ll) wG[from].size()-1});
            /*这里我之前把wG写成rG了，一直Wa,找了两天没找到原因，感谢尚位大佬帮我*/
    }
    
    void bfs(ll s) {
        
            memset(level, -1, sizeof(ll)*(n+2));
            queue<ll> que;
            level[s] = 0;
            que.push(s);
            while(!que.empty()) {
        
                    ll v = que.front(); que.pop();
                    for(ll i = 0; i < (ll)wG[v].size(); ++i) {
        
                            wedge &e = wG[v][i];
                            if(e.cap>0 && level[e.to]<0){
        
                                    level[e.to] = level[v] + 1;
                                    que.push(e.to);
                             }
                    }
            }
    }
    ll dfs(ll v, ll t, ll f) {
        
            if(v == t)      return f;
            for(ll &i = iter[v]; i < (ll)wG[v].size(); i++) {
        
                    wedge &e = wG[v][i];
                    if(e.cap > 0 && level[v] < level[e.to]) {
        
                            ll d = dfs(e.to, t, Min(f, e.cap));
                            if(d > 0){
        
                                    e.cap -= d;
                                    wG[e.to][e.rev].cap += d;
                                    return d;
                            }
                    }
    
            }
            return 0;
    }
    
    ll max_flow(ll s,ll t) {
        
            ll flow = 0;
            for(;;){
        
                    bfs(s);
                    if(level[t] < 0)        return flow;
                    memset(iter, 0, sizeof(ll)*(n+1));
                    ll f;
                    while((f = dfs(s, t, 0x3f3f3f3f3f3f3f3f)) > 0)
                            flow += f;
            }
    }
    
    int main(){
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            scanf("%lld",&t);
            while(t--){
        
                    scanf("%lld %lld",&n,&m);
                    for(ll i=0;i<=n;++i)
                    {
        
                            G[i].clear();
                            rG[i].clear();
                            wG[i].clear();
                    }
                    for(ll i=0, x, y, z;i<m;++i){
        
                            scanf("%lld %lld %lld",&x,&y,&z);
                            G[x].push_back((edge){
        y,z});
                            rG[y].push_back((edge){
        x,z});
                    }
                    dijkstra();
                    // cout<<"n:"<<n<<" dis[n]:"<<dis[n]<<endl;
                    for(ll u = 1; u <= n; ++u){
        
                            for(ll i = 0; i < (ll)G[u].size();++i){
        
                                    edge e = G[u][i];
                                    if(dis[u] + e.cost + rdis[e.to]==dis[n]){
        
                                            add_edge(u, e.to, e.cost);
                                            // printf("%lld %lld %lld\n",u,e.to, e.cost);
                                    }
                            }
                    }
                    cout<<max_flow(1,n)<<endl;
            }
    
    
            return 0;
    }

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