t開成n結果cur賦值的時候也只賦值到t令人智熄

【題目分析】

好吧我承認這個錯誤真的呵呵。。。。。。。。

題目有那~~~~~么長，然后畫畫圖這道題就基本看出正解了，再一看數據范圍，n<=500簡直良心，好了，網絡流沒得跑了。

因為按最短路進行傳遞，所以網絡流的建圖肯定是在最短路的基礎上，所以先進行一次SPFA。

考慮一條路如果加入網絡流的圖，那么這條路一定是在最短路上，dfs一次即可。

然后考慮拆點限制流量（一開始sb的寫成了邊權結果還跑過了樣例然后一交立馬咕咕），最后跑最大流即可。

PS：此題還有一個坑點，就是INF要設的很大很大，否則咕咕。

【代碼~】

#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL MAXN=1e3+10; const LL MAXM=4e5+10; const LL INF=0x3f3f3f3f3f;LL n,m,cnt,s,t; LL head[MAXN],cur[MAXN],depth[MAXN],val[MAXN]; LL nxt[MAXM],to[MAXM],w[MAXM]; LL cnt1,head1[MAXN]; LL nxt1[MAXM],to1[MAXM],w1[MAXM]; LL dis[MAXN],vis[MAXN];LL Read() {LL i=0,f=1;char c;for(c=getchar();(c>'9'||c<'0')&&c!='-';c=getchar());if(c=='-')f=-1,c=getchar();for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';return i*f; }void sc(LL x) {if(x>=10)sc(x/10);putchar(x%10+48); }void Add1(LL x,LL y,LL z) {cnt1++;nxt1[cnt1]=head1[x];head1[x]=cnt1;to1[cnt1]=y;w1[cnt1]=z; }void add1(LL x,LL y,LL z) {Add1(x,y,z);Add1(y,x,z); }void SPFA() {queue<LL> q;memset(dis,0x3f3f3f3f,sizeof(dis));dis[s]=0;q.push(s);while(!q.empty()){LL u=q.front();q.pop();vis[u]=0;for(LL i=head1[u];i!=-1;i=nxt1[i]){LL v=to1[i];if(dis[v]>dis[u]+w1[i]){dis[v]=dis[u]+w1[i];if(!vis[v]){vis[v]=1;q.push(v);}}}} }void Add(LL x,LL y,LL z) {nxt[cnt]=head[x];head[x]=cnt;to[cnt]=y;w[cnt]=z;cnt++; }void add(LL x,LL y,LL z) {Add(x,y,z);Add(y,x,0); }bool bfs() {queue<LL> q;memset(depth,0,sizeof(depth));depth[s]=1;q.push(s);while(!q.empty()){LL u=q.front();q.pop();for(LL i=head[u];i!=-1;i=nxt[i]){LL v=to[i];if(!depth[v]&&w[i]){depth[v]=depth[u]+1;q.push(v);}}}if(depth[t]==0)return false;return true; }LL dfs(LL u,LL dist) {if(u==t)return dist;for(LL &i=cur[u];i!=-1;i=nxt[i]){LL v=to[i];if(depth[v]==depth[u]+1&&w[i]){LL di=dfs(v,min(dist,w[i]));if(di>0){w[i]-=di;w[i^1]+=di;return di;}}}return 0; }LL dinic() {LL ans=0;while(bfs()){for(LL i=s;i<=t+n;++i)cur[i]=head[i];while(LL d=dfs(s,INF))ans+=d;}return ans; }void buildgraph(LL u,LL fa) {for(LL i=head1[u];i!=-1;i=nxt1[i]){LL v=to1[i];if(v==fa)continue;if(dis[v]==dis[u]+w1[i]){add(u+n,v,INF);buildgraph(v,u);}} }int main() {memset(head1,-1,sizeof(head1));memset(head,-1,sizeof(head));n=Read(),m=Read();s=1,t=n;for(LL i=1;i<=m;++i){LL x=Read(),y=Read(),z=Read();add1(x,y,z);}for(LL i=1;i<=n;++i)val[i]=Read();SPFA();buildgraph(1,-1);add(1,n+1,INF);for(LL i=2;i<n;++i)add(i,i+n,val[i]);sc(dinic());return 0; }

?

轉載于:https://www.cnblogs.com/Ishtar/p/10010755.html

總結

以上是生活随笔為你收集整理的洛谷3171 网络吞吐量（网络流）的全部內容，希望文章能夠幫你解決所遇到的問題。

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