hunnu--11545--小明的烦恼——找路径

小明的烦恼——找路径

Time Limit: 2000ms, Special Time Limit:5000ms, Memory Limit:32768KB

Total submit users: 45, Accepted users: 36

Problem 11545 : No special judgement

Problem description

小明真的是个非常厉害的人，每当老师有什么事时。总是会找到小明，二小明也总能解决。所以老师决定给小明一个奖励。给他额外的假期。小明当然非常高兴。由于小明最终能够如愿的出去旅游了。小明旅游的第一站到了漂亮的长沙。到了长沙当然免不了要去參观古色古香的的湖南师范大学了。小明在师大校园里愉快的玩耍，不时瞅一眼从他身边经过的美女。也感叹这个校园古老建筑带给他的震撼。

临近中午了。小明走到了理学院大门前，瞬间就被吸引了，于是就走了进去。在理学院的一个教室外面。小明看到有个带眼睛的男生在皱眉头，好像是被什么难题卡住了。小明的慈悲之心油然而生，于是就走了进去。

于是题目就来了：

有N个城市，有些城市有道路相连。但这些道路中间并没有加油站（每一个城市里面有加油站能够补给），如今有个project师要找到T条不同的路径从1号城市到N号城市。两条路径是不同的当且仅当不经过同样的边，如今告诉你project师的汽车的最大载油量C和经过每条道路所要消耗的油量，问你这个project师能不能完毕任务。

Input

由多组case：

每组case第一行有4个整数N，M。T，C，N<=200;C<=1000000;

然后有M行。每一行有3个整数，a，b。c，代表从a城市到b城市须要c的油量。

c<=1000000;假设两个城市之间有多条边。则视为不同的边。

Output

对于每一个case：

假设project师可以完毕任务，输出YES，不然输出NO。

Sample Input

Sample Output

YES

NO

Problem Source

HUNNU contest

题意：问能否找到t条从1到n的路径。每条不能有不论什么重叠，每小段路径能够走的条件是耗油量不大于c

解析：网络流水水就能飘过

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#define MAX(a,b) a>b?a:b

#define MIN(a,b) a<b?a:b

#define Max 1000000000

using namespace std;

int n,m,t,c,map[222][222];

int v[222],f[222],dis[222];

int EK()

{

    int i,j,k,l,cur,sum,mm,flag,num=0;

    while(true)

    {

        queue<int> q;

        memset(v,0,sizeof(v));//用来记录每次从1找到n的过程中每一个点是否被訪问

        memset(f,0,sizeof(f));//记录1到n的路径

        q.push(1);

        dis[1]=1<<30;

        flag=0;

        while(q.size())//直接广搜找一条从1到n的路径

        {

            cur=q.front();

            q.pop();

            for(i=2;i<=n;i++)

            if(!v[i]&&map[cur][i]<=c)//推断是否已经訪问过，耗油量是否同意通过

            {

                v[i]=1;

                q.push(i);

                f[i]=cur;//记录路径

                if(i==n){flag=1;break;}//假设找到了就标记并退出广搜

            }

        }

        if(!flag||num>=t)break;//假设没有找到从1到n的路径（即增广路）或者找到的路径数已经有了t条了。跳出循环

        num++;//找到路径数加一

        for(i=n;i!=1;i=f[i])//操作找到的这条路径

        {

            map[i][f[i]]=map[f[i]][i];//残余网络，给予网络流回流的机会（这里不能省。不要由于输入是双向就省略。当这段路径是回流路径的时候，它的反方向的值是max）

            map[f[i]][i]=Max;//正向初始化为max，表示已经被走过了，由于c再大也不会大于max

        }

    }

    if(num>=t)puts("YES");

    else puts("NO");

}

int main(void)

{

    int i,j,k,l;

    while(~scanf("%d%d%d%d",&n,&m,&t,&c))

    {

        for(i=1;i<=n;i++)

        for(j=1;j<=n;j++)

        {

            map[i][j]=Max;//各路段初始化为max，这样c再大也过不去

        }

        for(i=0;i<m;i++)

        {

            scanf("%d%d%d",&j,&k,&l);

            map[j][k]=l;//无向图建图

            map[k][j]=l;

        }

        EK();

    }

    return 0;

}