【网络流#1】hdu 3549

因为坑了无数次队友 要开始学习网络流了,先从基础的开始,嗯~

这道题是最大流的模板题,用来测试模板好啦~

Edmonds_Karp模板 with 前向星

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<queue>
 6 #define eps 0.000001
 7 #define MAXN 20
 8 #define MAXM 2005
 9 #define INF (1<<30)
10 using namespace std;
11 int i,j,k,n,m,x,y,T,head[MAXN],num,w,pre[MAXN],lin[MAXN];
12 struct edgenode
13 {
14     int to,next,w;
15 } map[MAXM];
16
17 void add_edge(int id,int x,int y,int w)
18 {
19     map[id].to=y;
20     map[id].w=w;
21     map[id].next=head[x];
22     head[x]=id;
23 }
24
25 bool bfs(int s,int t)
26 {
27     int u,v;
28     queue <int> q;
29     memset(pre,-1,sizeof(pre));
30     pre[s]=s;
31     q.push(s);
32     while(!q.empty())
33     {
34         u=q.front();
35         q.pop();
36         for(int i=head[u];i!=-1;i=map[i].next)
37         {
38             v=map[i].to;
39             if(pre[v]==-1&&map[i].w>0)
40             {
41                 pre[v]=u;
42                 lin[v]=i;
43                 if (v==t) return true;
44                 q.push(v);
45             }
46         }
47     }
48     return false;
49 }
50
51 int Edmonds_Karp(int s,int t)
52 {
53     int flow=0,d,i;
54     while(bfs(s,t))
55     {
56         d=INF;
57         for(i=t;i!=s;i=pre[i])
58             d=min(d,map[lin[i]].w);
59         for(i=t;i!=s;i=pre[i])
60         {
61             map[lin[i]].w-=d;
62             map[lin[i]^1].w+=d;
63         }
64         flow+=d;
65     }
66     return flow;
67 }
68
69 void init()
70 {
71     memset(head,-1,sizeof(head));
72     scanf("%d%d",&n,&m);
73     num=0;
74     for (i=0;i<m;i++)
75     {
76         scanf("%d%d%d",&x,&y,&w);
77         add_edge(i*2,x,y,w);
78         add_edge(i*2+1,y,x,0);
79     }
80 }
81
82 int main()
83 {
84     scanf("%d",&T);
85     for (int cas=1;cas<=T;cas++)
86     {
87         init();
88         printf("Case %d: %d\n",cas,Edmonds_Karp(1,n));
89     }
90 }

时间: 10-16

【网络流#1】hdu 3549的相关文章

网络流 HDU 3549 Flow Problem

网络流 HDU 3549 Flow Problem 题目:http://acm.hdu.edu.cn/showproblem.php?pid=3549 用增广路算法进行求解,注意的问题有两个: 1. 每次增广的时候,反向流量也要进行更行,一开始没注意,WA了几次 ORZ 2. 对于输入的数据,容量要进行累加更新. // 邻接矩阵存储 #include <bits/stdc++.h> using namespace std; const int INF = 0x7fffffff; const i

HDU 3549 Flow Problem 网络最大流问题 Edmonds_Karp算法

题目链接:HDU 3549 Flow Problem Flow Problem Time Limit: 5000/5000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 8218    Accepted Submission(s): 3824 Problem Description Network flow is a well-known difficult problem f

HDU 3549 Flow Problem ( 最大流 -EK 算法)

C++,G++的读取速度差距也太大了 Flow Problem 题意:n,m表示n个点m条有向带权边 问:从1-n最大流多少 裸最大流,拿来练手,挺不错的 #include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> const int N = 210; #define

【网络流】hdu 1569 方格取数(2)

/* 和1565一样: 总点数的权 - 最小覆盖点集 = 最大独立集 -------------------------------------- void add(int u, int v, int f)加边 { e[ct].u = u; e[ct].v = v; e[ct].f = f; next[ct] = first[u]; first[u] = ct++; e[ct].u = v; e[ct].v = u; e[ct].f = 0; next[ct] = first[v]; first

hdu 3549 Flow Problem(最大流模板题)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3549 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

hdu 3549 Flow Problem (网络最大流)

Flow Problem Time Limit: 5000/5000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 6674    Accepted Submission(s): 3112 Problem Description Network flow is a well-known difficult problem for ACMers. Given a graph, yo

hdu 3549 Flow Problem (最大流入门题)

增广路: 1 /************************************************************* 2 题目: Flow Problem(HDU 3549) 3 链接: http://acm.hdu.edu.cn/showproblem.php?pid=3549 4 题意: 给一个单向图,求从1到n的最大流 5 算法: 最大流之增广路(入门) 6 算法思想: 不断用BFS找通路,没每找一条路,记录这条路的最小流, 7 再给这条路上的所有流量减去这个最小值.

hdu 3549 Flow Problem 网络流

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3549 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

HDU 3549 Flow Problem (用一道最裸的最大流开启网络流算法之路)

Flow Problem Time Limit: 5000/5000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 9423    Accepted Submission(s): 4405 Problem Description Network flow is a well-known difficult problem for ACMers. Given a graph, y