HDU 3081 Marriage Match IV （SPFA+SAP）

Marriage Match IV

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1536    Accepted Submission(s): 437

Problem Description

Do not sincere non-interference。
Like that show, now starvae also take part in a show, but it take place between city A and B. Starvae is in city A and girls are in city B. Every time starvae can get to city B and make a data with a girl he likes. But there are two problems with it, one is starvae must get to B within least time, it's said that he must take a shortest path. Other is no road can be taken more than once. While the city starvae passed away can been taken more than once. 


So, under a good RP, starvae may have many chances to get to city B. But he don't know how many chances at most he can make a data with the girl he likes . Could you help starvae?

 

 

Input

The first line is an integer T indicating the case number.(1<=T<=65)
For each case,there are two integer n and m in the first line ( 2<=n<=1000, 0<=m<=100000 ) ,n is the number of the city and m is the number of the roads.

Then follows m line ,each line have three integers a,b,c,(1<=a,b<=n,0<c<=1000)it means there is a road from a to b and it's distance is c, while there may have no road from b to a. There may have a road from a to a,but you can ignore it. If there are two roads from a to b, they are different.

At last is a line with two integer A and B(1<=A,B<=N,A!=B), means the number of city A and city B.
There may be some blank line between each case.

 

 

Output

Output a line with a integer, means the chances starvae can get at most.

 

 

Sample Input

3 7 8 1 2 1 1 3 1 2 4 1 3 4 1 4 5 1 4 6 1 5 7 1 6 7 1 1 7 6 7 1 2 1 2 3 1 1 3 3 3 4 1 3 5 1 4 6 1 5 6 1 1 6 2 2 1 2 1 1 2 2 1 2

 

 

Sample Output

2 1 1

 

 

Author

starvae@HDU

 

 

Source

HDOJ Monthly Contest – 2010.06.05

 

 

Recommend

lcy

 

 

 

 

题意：求完全不同的最短路数目；

题解：先SPFA再用处于最短路上的边建图，容量1；

 

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

using namespace std;

const int EM=2010;
const int VM=500010;
const int INF=0x3f3f3f3f;

struct Edge{
    int u,v,nxt;
    int cap;
}edge[VM];

struct node{
    int v,w;
};

vector<node> vt[1010];

int n,m,cnt,head[VM],vis[VM],dis[VM];
int dep[VM],gap[VM],cur[VM],aug[VM],pre[VM];

void addedge(int cu,int cv,int cw){
    edge[cnt].u=cu;  edge[cnt].v=cv;  edge[cnt].cap=cw;
    edge[cnt].nxt=head[cu];  head[cu]=cnt++;
    edge[cnt].u=cv;  edge[cnt].v=cu;  edge[cnt].cap=0;
    edge[cnt].nxt=head[cv];  head[cv]=cnt++;
}

int src,des;

void SPFA(){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        dis[i]=INF;
    queue<int> q;
    while(!q.empty())
        q.pop();
    dis[src]=0;
    vis[src]=1;
    q.push(src);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=0;i<(int)vt[u].size();i++){
            int v=vt[u][i].v;
            if(dis[v]>dis[u]+vt[u][i].w){
                dis[v]=dis[u]+vt[u][i].w;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}

int SAP(int n){
    int max_flow=0,u=src,v;
    int id,mindep;
    aug[src]=INF;
    pre[src]=-1;
    memset(dep,0,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]=n;
    for(int i=0;i<=n;i++)
        cur[i]=head[i]; // 初始化当前弧为第一条弧
    while(dep[src]<n){
        int flag=0;
        if(u==des){
            max_flow+=aug[des];
            for(v=pre[des];v!=-1;v=pre[v]){     // 路径回溯更新残留网络
                id=cur[v];
                edge[id].cap-=aug[des];
                edge[id^1].cap+=aug[des];
                aug[v]-=aug[des];   // 修改可增广量，以后会用到
                if(edge[id].cap==0) // 不回退到源点，仅回退到容量为0的弧的弧尾
                    u=v;
            }
        }
        for(int i=cur[u];i!=-1;i=edge[i].nxt){
            v=edge[i].v;    // 从当前弧开始查找允许弧
            if(edge[i].cap>0 && dep[u]==dep[v]+1){  // 找到允许弧
                flag=1;
                pre[v]=u;
                cur[u]=i;
                aug[v]=min(aug[u],edge[i].cap);
                u=v;
                break;
            }
        }
        if(!flag){
            if(--gap[dep[u]]==0)    /* gap优化，层次树出现断层则结束算法 */
                break;
            mindep=n;
            cur[u]=head[u];
            for(int i=head[u];i!=-1;i=edge[i].nxt){
                v=edge[i].v;
                if(edge[i].cap>0 && dep[v]<mindep){
                    mindep=dep[v];
                    cur[u]=i;   // 修改标号的同时修改当前弧
                }
            }
            dep[u]=mindep+1;
            gap[dep[u]]++;
            if(u!=src)  // 回溯继续寻找允许弧
                u=pre[u];
        }
    }
    return max_flow;
}

int main(){

    //freopen("input.txt","r",stdin);

    int t;
    scanf("%d",&t);
    while(t--){
        cnt=0;
        memset(head,-1,sizeof(head));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            vt[i].clear();
        int u,v,w;
        node tmp;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&u,&v,&w);
            if(u==v)
                continue;
            tmp.v=v; tmp.w=w;
            vt[u].push_back(tmp);
        }
        scanf("%d%d",&src,&des);
        SPFA();
        for(int i=1;i<=n;i++)
            for(int j=0;j<(int)vt[i].size();j++)
                if(dis[vt[i][j].v]==dis[i]+vt[i][j].w)
                    addedge(i,vt[i][j].v,1);
        printf("%d\n",SAP(n));
    }
    return 0;
}