前言

這是評測記錄

---

正題

AC評測記錄鏈接：
https://www.luogu.org/record/show?rid=7945350

---

大意

一個圖，沒錯要求不能走重復的邊和點。求走最多次的情況下路最短。

---

解題思路

每次行走就是一個流量在流，然后將邊權設為1就可以保證邊只能走一次。之后就是點只能走一次，將一個點拆為入點和出點，連進來的連入點，連出去的連出點，然后之間連一條邊權為1的邊這樣那個點就只能走一次了。

---

代碼

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct line{int to,w,c,next; }a[100081]; int tot,n,m,s,t,f[501],ls[501],tail,answer; int state[501],x,y,w,c,ans,head,pre[501]; bool v[501]; void addl(int x,int y,int w,int c) {a[++tot].to=y;a[tot].w=w;a[tot].c=c;a[tot].next=ls[x];ls[x]=tot;a[++tot].to=x;a[tot].w=0;a[tot].c=-c;a[tot].next=ls[y];ls[y]=tot; } bool spfa() {for (int i=1;i<=t;i++)f[i]=2147483647;head=0;tail=1;v[s]=true;state[1]=s;f[s]=0;while (head!=tail){head=head%t+1;int x=state[head];for (int q=ls[x];q;q=a[q].next){int y=a[q].to;if (a[q].w&&f[x]+a[q].c<f[y]){f[y]=f[x]+a[q].c;pre[y]=q;if (!v[y]){v[y]=true;tail=tail%t+1;state[tail]=y;}}}v[x]=false;}if (f[t]==2147483647) return 0;else return 1; } void upway() {int now;ans+=f[t];now=t;answer+=1;while (now!=s){a[pre[now]].w--;a[pre[now]^1].w++;now=a[pre[now]^1].to;} } int main() {tot=1;scanf("%d%d",&n,&m);s=1;t=2*n;addl(s,2,2147483647,0);addl(t-1,t,2147483647,0);//起點和終點可以走無數(shù)遍for (int i=2;i<n;i++)addl(i*2-1,i*2,1,0);//連入點和出點for (int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&c);addl(x*2,y*2-1,1,c);//連接}while (spfa()) upway();printf("%d %d",answer,ans); }

總結

以上是生活随笔為你收集整理的P2153-晨跑【费用流,网络流,拆点】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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