//RQ的板子真的很好用 #include<cstdio> #include<cstring> #include<queue> #define INF 1e9 using namespace std; const int maxn=200+5;struct Edge {int from,to,cap,flow;Edge(){}Edge(int f,int t,int c,int flow):from(f),to(t),cap(c),flow(flow){} };struct Dinic {int n,m,s,t;vector<Edge> edges;vector<int> G[maxn];bool vis[maxn];int cur[maxn];int d[maxn];void init(int n,int s,int t){this->n=n, this->s=s, this->t=t;edges.clear();for(int i=1;i<=n;i++) G[i].clear();}void AddEdge(int from,int to,int cap){edges.push_back(Edge(from,to,cap,0));edges.push_back(Edge(to,from,0,0));m = edges.size();G[from].push_back(m-2);G[to].push_back(m-1);}bool BFS(){memset(vis,0,sizeof(vis));queue<int> Q;d[s]=0;Q.push(s);vis[s]=true;while(!Q.empty()){int x=Q.front(); Q.pop();for(int i=0;i<G[x].size();i++){Edge& e=edges[G[x][i]];if(!vis[e.to] && e.cap>e.flow){vis[e.to]=true;Q.push(e.to);d[e.to]= 1+d[x];}}}return vis[t];}int DFS(int x,int a){if(x==t || a==0) return a;int flow=0,f;for(int& i=cur[x]; i<G[x].size(); i++){Edge& e=edges[G[x][i]];if(d[x]+1==d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow) ))>0 ){e.flow+=f;edges[G[x][i]^1].flow -=f;flow+=f;a-=f;if(a==0) break;}}return flow;}int Maxflow(){int flow=0;while(BFS()){memset(cur,0,sizeof(cur));flow += DFS(s,INF);}return flow;} }DC;int main() {int n,m;while(scanf("%d%d",&m,&n)==2){DC.init(n,1,n);while(m--){int u,v,w;scanf("%d%d%d",&u,&v,&w);DC.AddEdge(u,v,w);}printf("%d\n",DC.Maxflow());}return 0; }

?

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的图论-网络流-Dinic （邻接表版）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。