HDU 5294 多校第一场1007题 最短路+最小割

　　　　　　　　　　　　　　　　　　　　Tricks Device

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1285    Accepted Submission(s): 302

Problem Description

Innocent Wu follows Dumb Zhang into a ancient tomb. Innocent Wu’s at the entrance of the tomb while Dumb Zhang’s at the end of it. The tomb is made up of many chambers, the total number is N. And there are M channels connecting the chambers. Innocent Wu wants to catch up Dumb Zhang to find out the answers of some questions, however, it’s Dumb Zhang’s intention to keep Innocent Wu in the dark, to do which he has to stop Innocent Wu from getting him. Only via the original shortest ways from the entrance to the end of the tomb costs the minimum time, and that’s the only chance Innocent Wu can catch Dumb Zhang.
Unfortunately, Dumb Zhang masters the art of becoming invisible(奇门遁甲) and tricks devices of this tomb, he can cut off the connections between chambers by using them. Dumb Zhang wanders how many channels at least he has to cut to stop Innocent Wu. And Innocent Wu wants to know after how many channels at most Dumb Zhang cut off Innocent Wu still has the chance to catch Dumb Zhang.

 

Input

There are multiple test cases. Please process till EOF.
For each case,the first line must includes two integers, N(<=2000), M(<=60000). N is the total number of the chambers, M is the total number of the channels.
In the following M lines, every line must includes three numbers, and use ai、bi、li as channel i connecting chamber ai and bi(1<=ai,bi<=n), it costs li(0<li<=100) minute to pass channel i.
The entrance of the tomb is at the chamber one, the end of tomb is at the chamber N.

 

Output

Output two numbers to stand for the answers of Dumb Zhang and Innocent Wu’s questions.

 

Sample Input

8 9

1 2 2

2 3 2

2 4 1

3 5 3

4 5 4

5 8 1

1 6 2

6 7 5

7 8 1

 

Sample Output

2 6

 

Author

FZUACM

 

Source

2015 Multi-University Training Contest 1

 

 

题意：

吴天真和张起灵分别在一个墓地的入口和出口

吴天真准备到出口找张起灵

已知这个墓地有N个房间,入口编号为1，出口编号为N，这N个房间有M条隧道连接

给出吴天真经过每一个隧道需要的时间

设吴天真从入口到达出口的最短时间为T

则张只会在出口处逗留T的时间，超过这个时间张就会离开，天真就再也找不到他了

由于张不希望被天真找到，所以张会施展他的奇门遁甲：

张可以指定若干隧道，被指定的隧道将会消失。

 

现在问题来啦：

张问你：他最少需要指定多少条隧道，才可以保证天真找不到他

天真也要问你：在保证天真可以找得到张的情况下， 张最多可以指定多少条隧道消失。

 

分析：

由于天真从1到达N所走的路径必须是最短路径，所以若一条路径不是最短路径，就不用管它了。

从1到N的最短路径不止一条，那么天真的问题等价为：

天真走那条隧道数最少的最短路径，若有x条边，则第二问的答案为总隧道数-x

如果对这个图重新建立，只保留所有的最短路径的边，则张的问题等价为：

求出这个新图的最小割。

 

而我们知道，一个图的最小割就等于最大流，所以求最大流就可以了。

而他要求的是最小割的边的总数啊？

只要我们建立新图的时候，把边的容量初始化为1，那么最后求得的最大流=最小割=最小割的边数

 

不过，我又有一个想法，如果先用dinic求出最大流，在level[T]<0的时候，对这个图的每一个节点，若level[i]>=0

则i是在集合S，若level[i]<0,则i是在集合T

然后遍历每一条边，如果边的起点在S，终点在T，则边数++

遍历完成后，边数就是割的边数了。

不过这样wa了，这个想法可以？我再去想想。

 

 

所以算法流程为：

1.保证天真走的是最短路的条件下，从1到达N的最少隧道数。

2.只保留所有的最短路径的边，建立新图

3.求出这个图的最大流

 

这道题我遇见了几个很好的情况，也说说：

1.以前做的题只要求出最短路的长度就可以了，这个要求的是最短路中边数最少的那一条路径的边数

做法：

加一个cnt数组，cnt[i]表示节点i到起点的最短路的最少边数

cnt[起点]=0,cnt[其他]=INF

然后spfa的同时更新cnt的值就好了

 

2.找出1到N所有的最短路径的边，建立新图

做法：

在求出起点到所有点的最短路径dis后，

遍历每一条边e，若dis[e.to]==dis[e.from]+e.cost

则边e是起点1到达点e.to的其中一条最短路径的边，加入，容量这道题是1

因为这条边有可能就是起点1到终点N的其中一条最短路径的边

 

3.求最小割的边数

做法：

当所有边的容量都是1的时候，最小割的边数=最小割=最大流

 

 

 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

using namespace std;

const int  MAXN=2010;
const int INF=0x3f3f3f3f;

struct Edge1
{
    int to,cost;
};
struct Edge2
{
    int to,cap,rev;
};

vector<Edge1>edge1[MAXN];
vector<Edge2>edge2[MAXN];

void addedge1(int from,int to,int cost)
{
    edge1[from].push_back((Edge1){to,cost});
    edge1[to].push_back((Edge1){from,cost});
}
void addedge2(int from,int to,int cap)
{
    edge2[from].push_back((Edge2){to,cap,edge2[to].size()});
    edge2[to].push_back((Edge2){from,0,edge2[from].size()-1});
}

int iter[MAXN];
int level[MAXN];
int in[MAXN];   //求割的时候
int vis[MAXN];
int dis[MAXN];
int cnt[MAXN];

void init(int N)
{
    for(int i=0;i<=N;i++)
    {
        edge1[i].clear();
        edge2[i].clear();
    }
}

void spfa(int N)
{
    for(int i=1;i<=N;i++)
    {
        dis[i]=INF;
        cnt[i]=INF;
    }
    memset(vis,false,sizeof(vis));

    queue<int>que;
    while(!que.empty())
        que.pop();

    int str=1;
    que.push(str);
    vis[str]=true;
    dis[str]=0;
    cnt[str]=0;

    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;   //重要
        for(int i=0;i<edge1[u].size();i++)
        {
            Edge1 &e=edge1[u][i];
            if(dis[e.to]==dis[u]+e.cost)
                cnt[e.to]=min(cnt[e.to],cnt[u]+1);
            if(dis[e.to]>dis[u]+e.cost)
            {
                dis[e.to]=dis[u]+e.cost;
                cnt[e.to]=cnt[u]+1;
                if(!vis[e.to])
                {
                    vis[e.to]=true;
                    que.push(e.to);
                }
            }
        }
    }
    return ;
}

void build_group(int N)
{
    for(int i=1;i<=N;i++)
    {
        for(int j=0;j<edge1[i].size();j++)
        {
            Edge1 &e=edge1[i][j];
            if(dis[e.to]==dis[i]+e.cost)
                addedge2(i,e.to,1);
        }
    }
}

void bfs()
{
    memset(level,-1,sizeof(level));
    queue<int>que2;
    while(!que2.empty())
        que2.pop();
    int s=1;
    que2.push(s);
    level[1]=0;
    while(!que2.empty())
    {
        int u=que2.front();
        que2.pop();
        for(int i=0;i<edge2[u].size();i++)
        {
            Edge2 &e=edge2[u][i];
            if(e.cap>0&&level[e.to]<0)
            {
                level[e.to]=level[u]+1;
                que2.push(e.to);
            }
        }
    }
}

int dfs(int u,int T,int f)
{
    if(u==T)
        return f;
    for(int &i=iter[u];i<edge2[u].size();i++)
    {
        Edge2 &e=edge2[u][i];
        if(e.cap>0&&level[e.to]>level[u])
        {
            int d=dfs(e.to,T,min(e.cap,f));
            if(d>0)
            {
                e.cap-=d;
                edge2[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

/*
int solve(int N)
{
    for(int i=1;i<=N;i++)
        in[i]=false;
    for(int i=1;i<=N;i++)
    {
        if(level[i]>=0)
            in[i]=true;
    }

    int res=0;

    for(int i=1;i<=N;i++)
    {
        if(!in[i])
            continue;
        for(int j=0;j<edge2[i].size();j++)
        {
            Edge2 &e=edge2[i][j];
            if(!in[e.to])
                res++;
        }
    }
    return res;
}
*/

int max_flow(int N)
{
    int flow=0;
    while(1)
    {
        bfs();
        if(level[N]<0)
            break;
        memset(iter,0,sizeof(iter));
        int f;
        while(f=dfs(1,N,INF))
        {
            flow+=f;
        }
    }
    //return solve(N);
    return flow;
}

int main()
{
    int N,M;
    while(~scanf("%d%d",&N,&M))
    {
        init(N);

        for(int i=1;i<=M;i++)
        {
            int from,to,cost;
            scanf("%d%d%d",&from,&to,&cost);
            addedge1(from,to,cost);
        }

        spfa(N);

        build_group(N);

        int cut=max_flow(N);

        printf("%d %d
",cut,M-cnt[N]);
    }
    return 0;
}