HDU 3549 Flow Problem(有向边网络流)
题意:T个测试数据下面n,m表示n个点m条有向带权边
m条边
问:从1-n最大流多少
测板子的题目,没啥思路
下面用的是dinic,开始没有考虑反向弧debug了好久,附赠一大坨测试数据
#include <iostream> #include <string> #include <cstring> #include <algorithm> #include <cstdio> #include <cctype> #include <queue> #include <stdlib.h> #include <cstdlib> #include <math.h> #include <set> #include <vector> #define inf 100000000 #define eps 1e-8 #define N 205 #define M 1050 #define ll int using namespace std; inline ll Max(ll a,ll b){return a>b?a:b;} inline ll Min(ll a,ll b){return a<b?a:b;} //M为边数 N为点数 从1-n //M为边数 N为点数 从1-n struct Edge{ int from,to,flow,cap, nex; }edge[M*2];//双向边,注意RE 注意这个模版是 相同起末点的边 合并而不是去重 int head[N],edgenum;//2个要初始化-1和0 void addedge(int u,int v,int cap){//网络流要加反向弧 Edge E={u,v,0,cap,head[u]}; edge[edgenum]=E; head[u]=edgenum++; Edge E2={v,u,0,0,head[v]}; //这里的cap若是单向边要为0 edge[edgenum]=E2; head[v]=edgenum++; } int dis[N],cur[N];//距离起点的距离 cur[i]表示i点正在考虑的边 优化不再考虑已经用过的点 初始化为head bool vis[N]; bool BFS(int Start,int End){ memset(vis,0,sizeof(vis)); memset(dis,-1,sizeof(dis)); queue<int>Q; while(!Q.empty())Q.pop(); Q.push(Start); dis[Start]=0; vis[Start]=1; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i=head[u];i!=-1;i=edge[i].nex){ Edge E =edge[i]; if(!vis[E.to] && E.cap>E.flow) { vis[E.to]=1; dis[E.to]=dis[u]+1; if(E.to==End)return true; Q.push(E.to); } } } return false; } int DFS(int x, int a,int End){//流入x 的流量是a if(x==End || a==0)return a; int flow = 0, f; for(int& i=cur[x];i!=-1;i=edge[i].nex) { Edge& E = edge[i]; if(dis[x]+1 == dis[E.to] && (f = DFS(E.to , Min(a, E.cap-E.flow), End))>0 ) { E.flow += f; edge[ i^1 ].flow -= f;//反向边要减掉 flow += f; a -= f; if(a==0)break; } } return flow; } int Maxflow(int Start,int End){ int flow=0; while(BFS(Start,End)){ memcpy(cur,head,sizeof(head));//把head的数组复制过去 flow += DFS(Start, inf, End); } return flow; } int main() { int T,Cas=1,n,m,i,a,b,c;scanf("%d",&T); while (T--) { memset(head,-1,sizeof(head)); edgenum=0; scanf("%d %d",&n,&m); while(m--) { scanf("%d %d %d",&a,&b,&c); addedge(a,b,c); } printf("Case %d: %d\n",Cas++,Maxflow(1,n)); } return 0; } /* 99 3 2 1 2 1 2 3 1 3 3 1 2 1 2 3 1 1 3 1 3 2 1 3 2 1 3 5 3 2 1 2 456 1 2 56431 3 3 1 3 100 1 1 100 1 1 100 11 15 1 2 1 1 3 1 1 4 1 2 5 1 2 6 1 3 7 1 3 8 1 4 9 1 4 10 1 5 11 1 6 11 1 7 11 1 8 11 1 9 11 1 10 11 1 11 15 1 2 2 1 3 2 1 4 2 2 5 1 2 6 1 3 7 1 3 8 1 4 9 1 4 10 1 5 11 1 6 11 1 7 11 1 8 11 1 9 11 1 10 11 1 11 15 1 2 2 1 3 1 1 4 2 2 5 1 2 6 1 3 7 1 3 8 1 4 9 1 4 10 1 5 11 1 6 11 1 7 11 1 8 11 1 9 11 1 10 11 1 2 0 2 1 1 2 4651 4 4 1 2 10 2 1 5 2 4 20 1 3 3 4 5 1 2 10 2 1 5 2 4 20 1 3 3 3 4 1 9 10 1 5 2 2 4 6 2 3 4 1 2 9 3 9 5 5 9 4 2 3 1 4 2 1 6 7 1 3 7 2 4 4 1 2 10 1 3 2 3 4 1 2 4 1 4 4 1 2 1 1 3 1 3 4 10 2 4 10 ans: 1 2 7 0 100 3 6 5 0 4651 10 11 7 2 2 */
补充:软件开发 , C++ ,