hunnu 11545小明的烦恼——找路径 (最大流)

小明的烦恼——找路径 
Time Limit: 2000ms, Special Time Limit:5000ms,
Memory Limit:32768KB
Total submit users: 45, Accepted users:
37
Problem 11545 : No special judgement
Problem description
  小明真的是个很厉害的人,每当老师有什么事时,总是会找到小明,二小明也总能解决,所以老师决定给小明一个奖励,给他额外的假期。小明当然很高兴,因为小明终于可以如愿的出去旅游了。小明旅游的第一站到了美丽的长沙,到了长沙当然免不了要去参观古色古香的的湖南师范大学了,小明在师大校园里愉快的玩耍,不时瞅一眼从他身边经过的美女,也感叹这个校园古老建筑带给他的震撼。临近中午了,小明走到了理学院大门前,瞬间就被吸引了,于是就走了进去,在理学院的一个教室外面,小明看到有个带眼睛的男生在皱眉头,好像是被什么难题卡住了,小明的慈悲之心油然而生,于是就走了进去。于是题目就来了:

有N个城市,有些城市有道路相连,但这些道路中间并没有加油站(每个城市里面有加油站可以补给),现在有个工程师要找到T条不同的路径从1号城市到N号城市,两条路径是不同的当且仅当不经过相同的边,现在告诉你工程师的汽车的最大载油量C和经过每条道路所要消耗的油量,问你这个工程师能不能完成任务。

Input
  由多组case:

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

然后有M行。每一行有3个整数,a,b,c,代表从a城市到b城市需要c的油量。c<=1000000;如果两个城市之间有多条边,则视为不同的边。

Output
  对于每个case:

如果工程师能够完成任务,输出YES,不然输出NO。

Sample Input
7 9 2 5
1 2 2
2 3 5
3 7 5
1 4 1
4 3 1
4 5 7
5 7 1
1 6 3
6 7 3
7 9 2 4
1 2 2
2 3 5
3 7 5
1 4 1
4 3 1
4 5 7
5 7 1
1 6 3
6 7 3
Sample Output
YES
NO
解题:假设每条可行边的流限最大为1,则根据网络流的性质:每个点的 流进量==流出量,守恒。所以一条边只能属于一条路。
#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
const int N = 225;

bool mapt[N][N];
int pre[N],sNode,eNode,n;

bool searchPath(){//找一条增广路
    queue<int>q;
    bool vist[N]={0};
    pre[sNode]=sNode; vist[sNode]=1;
    q.push(sNode);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int v=2; v<=n; v++)
        if(mapt[u][v]&&vist[v]==0){
            vist[v]=1;
            pre[v]=u;
            if(v==eNode) return true;
            q.push(v);
        }
    }
    return false;
}
bool maxflow(int T){
    while(searchPath()){
        int u,v;
        T--;
        if(T<=0)return true;
        v=eNode;
        while(v!=sNode){
            u=pre[v];
            mapt[u][v]=0;
            mapt[v][u]=1;//可以回流
            v=u;
        }
    }
    return false;
}
int main(){
    int M,T,C,a,b,c;
    while(scanf("%d%d%d%d",&n,&M,&T,&C)>0){
        memset(mapt,false,sizeof(mapt));
        sNode=1; eNode=n;
        while(M--){
            scanf("%d%d%d",&a,&b,&c);
            if(c<=C) mapt[a][b]=1;//每条边的最大流限。
        }
        if(T==0||maxflow(T))
        printf("YES\n");
        else printf("NO\n");
    }
}

时间: 06-07

hunnu 11545小明的烦恼——找路径 (最大流)的相关文章

hunnu - 11545 小明的烦恼——找路径 (最大流)

http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11545 只是要求不经过相同的边,那么每次找出一条增广路T--,判断T<=0即可. 在加边的时候注意要c<=C的时候才需要加边. 邻接表: 1 # include <cstdio> 2 # include <cstring> 3 # include <algorithm> 4 # include <iostream&

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   小明真的是个很厉害的人,每当老师有什么事时,总是会找到小明,二小明也总能解决,所以老师决定给小明一个奖励,给他额外的假期.小明当然很高兴

hunnu 小明的烦恼——找字符串

http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11544&courseid=0 小明的烦恼——找字符串 Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB Total submit users: 108, Accepted users: 68 Problem 11544 : No special judgement Probl

hunnu11544:小明的烦恼——找字符串

Problem description   小明是个很优秀的同学,他除了特别公正外,他也很细心,当然老师肯定也知道,这不,老师又有事情找他帮忙了,老师每周都会给他一个字符串A,然后问小明"A字符串的循环移位产生的所有字符串中,字典序最小的是哪个",于是小明屁颠屁颠的一个一个比对,但是长久下来,小明实在是受不了了,所以他想请你帮帮他.同样,你帮他解决,你就会多AC一个题目. Hint: 如果A字符串为bcda,那么其所有的循环移位的新字符串有cdab,dabc,abcd,和他自己bcda

hnuun 11544 小明的烦恼——找字符串(字符串)

http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11544&courseid=0 最小最大表示法: 求环形字符串的最小最大字典序: 参考:http://www.cnblogs.com/ziyi--caolu/p/3245132.html 最小表示法: 初始时,i=0,j=1,分别以i,j,为起始点顺着i,j,往下比较直到找的str[i+k]!=str[j+k],然后分两种情况考虑: 1.  str[i+k]&g

hunnu11543:小明的烦恼——分糖果

Problem description   小明在班里一直是个非常公正的孩子.这点同学和老师都非常清楚,这不,老师每周都会从家里带来一些糖果.然后叫小明把糖果分给其它小朋友,但这个班里的同学都有一个非常特别的性格,就是他们仅仅喜欢偶数.对于糖果也一样,所以小明在分糖果时也必需要保证这一点,即使每一个同学分的糖果数量不一样.都是奇怪的是,小明有时候并不可以合格的分糖果,这让他大为苦恼.害怕别的同学会不再信任他(虽然其它同学不会这么想).所以他想请你帮帮他.在每次老师把糖果给他时,就帮他推断出糖果能

擅长排列的小明 II(找规律)

擅长排列的小明 II 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述 小明十分聪明,而且十分擅长排列计算. 有一天小明心血来潮想考考你,他给了你一个正整数n,序列1,2,3,4,5......n满足以下情况的排列: 1.第一个数必须是1 2.相邻两个数之差不大于2 你的任务是给出排列的种数. 输入 多组数据.每组数据中输入一个正整数n(n<=55). 输出 输出种数. 样例输入 4 样例输出 4 dp[i]=dp[i-1]+dp[i-3]+1; 题目大意:给出1-n

【贪心+堆】XMU 1584 小明的烦恼

题目链接: http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1584 题目大意: 给n(n<=100 000)个任务的耗时和截至时间,问最少不能完成几个任务. 题目思路: [贪心+堆] 一开始想贪心但是没想到要加个堆,又跪了. 首先按照结束时间排序,结束时间早的肯定优先考虑. 如果当前的任务无法完成,就将当前任务和之前已经做了的任务中耗时最长的取消掉,改做当前任务 (如果当前任务就是耗时最长的则不用加当前任务,因为取消一个换另一个结果不会更差,只

小明系列问题――小明序列(LIS)

小明系列问题――小明序列 Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Practice HDU 4521 Description 大家都知道小明最喜欢研究跟序列有关的问题了,可是也就因为这样,小明几乎已经玩遍各种序列问题了.可怜的小明苦苦地在各大网站上寻找着新的序列问题,可是找来找去都是自己早已研究过的序列.小明想既然找不到,那就自己来发明一个新的序列问题吧!