題意:
? ? ? x最小的到x最大的點同一時間的最大運輸量.


思路:

? ? ? 裸的最大流,不解釋,注意一點,記得加上防爆棧.

#pragma comment(linker, "/STACK:1024000000,1024000000") #include<stdio.h> #include<string.h> #include<queue> #define N 300000 using namespace std; struct star {int b,c,next; }D[N]; struct mknum {int x,t; }tou,xin; queue<mknum>q; int minn(int x,int y) {return x<y?x:y; } int list1[100005],list2[100005],tot; int deep[100005]; void add(int a,int b,int c) {D[++tot].b=b;D[tot].c=c;D[tot].next=list1[a];list1[a]=tot; } bool bfs(int s,int t,int n) {memset(deep,255,sizeof(deep));deep[s]=0;xin.x=s;xin.t=0;while(!q.empty())q.pop();q.push(xin);while(!q.empty()){tou=q.front();q.pop();for(int k=list1[tou.x];k;k=D[k].next){int to=D[k].b;if(deep[to]==-1&&D[k].c){xin.x=to;xin.t=tou.t+1;q.push(xin);deep[xin.x]=xin.t;}}}for(int i=0;i<=n;i++)list2[i]=list1[i];return deep[t]!=-1; } int dfs(int s,int t,int flow) {if(s==t)return flow;int nowflow=0;for(int k=list2[s];k;k=D[k].next) {list2[s]=k;int to=D[k].b;int c=D[k].c;if(deep[to]!=deep[s]+1||!c)continue;if(nowflow==flow)break;int temp=dfs(to,t,minn(c,flow-nowflow));nowflow+=temp;D[k].c-=temp;D[k^1].c+=temp;if(nowflow==flow)break;} if(nowflow==0)deep[s]=0;return nowflow; }int DINIC(int s,int t,int n) {int ans=0;while(bfs(s,t,n)){ans+=dfs(s,t,1000000000);}return ans; }int main () {int i,n,m,mx,mi,s,t,tt,a,b,c,x,y;scanf("%d",&tt);while(tt--){scanf("%d%d",&n,&m);mx=-10000000,mi=10000000;for(i=1;i<=n;i++){scanf("%d%d",&x,&y);if(mx<x){mx=x;t=i;}if(mi>x){mi=x;s=i;}}memset(list1,0,sizeof(list1));tot=1;for(i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);add(a,b,c); add(b,a,c);}printf("%d\n",DINIC(s,t,n));}return 0; }

總結

以上是生活随笔為你收集整理的hdu4280 最大流DINIC的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。