文档章节

Flow Problem

o
 osc_1ee7cxmx
发布于 2018/08/06 20:57
字数 595
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

Flow Problem

TimeLimit:5000MS  MemoryLimit:32768KB
64-bit integer IO format: %I64d
 
Problem Description
Network flow is a well-known difficult problem for ACMers. Given a graph, your task is to find out the maximum flow for the weighted directed graph.
Input
The first line of input contains an integer T, denoting the number of test cases. 
For each test case, the first line contains two integers N and M, denoting the number of vertexes and edges in the graph. (2 <= N <= 15, 0 <= M <= 1000) 
Next M lines, each line contains three integers X, Y and C, there is an edge from X to Y and the capacity of it is C. (1 <= X, Y <= N, 1 <= C <= 1000)
Output
For each test cases, you should output the maximum flow from source 1 to sink N.
SampleInput
2
3 2
1 2 1
2 3 1
3 3
1 2 1
2 3 1
1 3 1
SampleOutput
Case 1: 1
Case 2: 2
题解:模板题,求最大流量
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int maxn=1000;
  4 const int inf=0x3f3f3f3f;
  5 struct node
  6 {
  7     int to,flow,next;
  8 } edge[maxn*4];
  9 int first[maxn],sign,vis[maxn],pre[maxn];
 10 void init()
 11 {
 12     memset(first,-1,sizeof(first));
 13     sign=0;
 14 }
 15 void add_edge(int u,int v,int flow)
 16 {
 17     edge[sign].to=v;
 18     edge[sign].flow=flow;
 19     edge[sign].next=first[u];
 20     first[u]=sign++;
 21     edge[sign].to=u;
 22     edge[sign].flow=0;///建一条反向边,流量为0;
 23     edge[sign].next=first[v];
 24     first[v]=sign++;
 25 }
 26 bool bfs(int s,int t)
 27 {
 28     memset(vis,0,sizeof(vis));
 29     memset(pre,-1,sizeof(pre));
 30        vis[s]=1;
 31        queue<int >que;
 32        que.push(s);
 33        while(!que.empty())
 34        {
 35            int now=que.front();
 36            que.pop();
 37            if(now==t)
 38            {
 39                return 1;
 40            }
 41            for(int i=first[now];~i;i=edge[i].next)
 42            {
 43                int to=edge[i].to,flow=edge[i].flow;
 44                if(!vis[to]&&flow>0)
 45                {
 46                    vis[to]=1;
 47                    que.push(to);
 48                    pre[to]=i;///记录路径  记录的是由上一条边到to这个点
 49                }
 50            }
 51        }
 52        return 0;
 53 
 54 }
 55 int edomon_krap(int s,int t)///起点 终点
 56 {
 57     int max_flow=0;
 58     while(bfs(s,t))
 59     {
 60         int min_flow=inf;
 61         int x=t;
 62         while(x!=s)
 63         {
 64            // printf("%d\n",x);
 65             int index=pre[x];
 66             //printf("intdex  %d\n",index);
 67             min_flow=min(min_flow,edge[index].flow);
 68             x=edge[index^1].to;
 69              //printf("x==%d\n",x);
 70         }
 71          x=t;
 72         while(x!=s)
 73         {
 74             int index=pre[x];
 75             edge[index].flow-=min_flow;
 76             edge[index^1].flow+=min_flow;///反向边加上min_flow
 77             x=edge[index^1].to;
 78         }
 79         max_flow+=min_flow;
 80 
 81     }
 82    return max_flow;
 83 }
 84 int main()
 85 {
 86     int t,n,m;
 87     scanf("%d",&t);
 88     for(int i=1;i<=t;i++)
 89     {
 90         init();
 91         scanf("%d%d",&n,&m);
 92         for(int j=1;j<=m;j++)
 93         {
 94             int u,v,w;
 95             scanf("%d%d%d",&u,&v,&w);
 96             add_edge(u,v,w);
 97         }
 98         printf("Case %d: %d\n",i,edomon_krap(1,n));
 99     }
100 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Hacker News 简讯 2020-07-11

更新时间: 2020-07-11 00:00 Scientists make precise edits to mitochondrial DNA for first time - (nature.com) 科学家首次对线粒体DNA进行精确编辑 得分:66 | 评论:4 LibreOffice: The N......

FalconChen
36分钟前
95
0
是否有可能从另一个git存储库中挑选一个提交? - Is it possible to cherry-pick a commit from another git repository?

问题: I'm working with a git repository that needs a commit from another git repository that knows nothing of the first. 我正在使用一个git存储库,需要从另一个不知道第一个存储库......

技术盛宴
昨天
26
0
【LeetCode】53 盛最多水的容器

题目 解题思路 双指针法: https://leetcode-cn.com/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/ 代码 public class Solution { ......

JaneRoad
昨天
20
0
阿里云OSS配置CDN加速

首先购买CDN流量包 然后添加域名 添加好后 然后将域名OSS.xxxx.com 解析到 生成的CDN域名上 这样就完成了

可达鸭眉头一皱
昨天
16
0
js 整数与小数正则替换片段

说明 /(\d+)/g 整数 /(\d+\.\d+)rem/g 小数 /(\d+\.\d+|\d+)rem/g 其中 | 或 条件 例子 全局查找带 rem 单位的,替换成 px 单位 let text = text.replace(/(\d+\.\d+|\d+)rem/g, function(s......

DrChenXX
昨天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部