题面：
思路：
一个点只能走一回，路径不能相交......
显然可以转化为网络流的决策来做
我们构建一个网络，令其最大流等于最大的跑步天数即可
怎么构造呢？
对于每个点只能走一次的限制，可以考虑拆点，将每个点（除了起点和终点）拆成两个，中间连一条容量为1的边，就可以了
同时，因为要求走的距离最短，那么给每一条原图中的边赋一个费用，把最大流改成费用流即可
这道题有一个值得深思的地方：是题目中的哪个点让你想到要用网络流而不是别的算法来做的？
这道题我实际上是抱着“网络流那么厉害，说不定就做得了”这样的想法
但是肯定不能看到什么题都往每一个算法上面靠，效率太低了
不过有的题在这方面就很明显
例如一些出入口固定的问题，显然就是dp或者网络流（深海机器人，AGC002某题）
实际上，我们见到的题目里面，会明确告诉你算法的题目并不多，而且这种题目一般都比较难
因此还是要培养自己看出算法来的能力啊
Code：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define inf 1e9 6 using namespace std; 7 inline int read(){ 8 int re=0,flag=1;char ch=getchar(); 9 while(ch>'9'||ch<'0'){ 10 if(ch=='-') flag=-1; 11 ch=getchar(); 12 } 13 while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar(); 14 return re*flag; 15 } 16 int n,m,cnt=-1,first[10010],dis[10010],vis[10010],ans; 17 struct edge{ 18 int to,next,w,cap; 19 }a[200010]; 20 inline void add(int u,int v,int cap,int w){ 21 //cout<<u<<" "<<v<<" "<<cap<<" "<<w<<" "; 22 a[++cnt]=(edge){v,first[u],w,cap};first[u]=cnt; 23 a[++cnt]=(edge){u,first[v],-w,0};first[v]=cnt; 24 } 25 int q[200010]; 26 bool spfa(int s,int t){ 27 int i,u,v,head=0,tail=1;memset(q,0,sizeof(q)); 28 for(i=1;i<=(n<<1);i++) dis[i]=-1;memset(vis,0,sizeof(vis)); 29 dis[t]=0;q[0]=t;vis[t]=1; 30 while(head<tail){ 31 u=q[head++];vis[u]=0; 32 //cout<<"spfa "<<u<<" "<<dis[u]<<" "; 33 for(i=first[u];~i;i=a[i].next){ 34 v=a[i].to; 35 //cout<<" to "<<v<<" "<<dis[v]<<" "<<a[i^1].cap<<" "; 36 if(!a[i^1].cap) continue; 37 if(~dis[v]&&dis[v]<=dis[u]+a[i^1].w) continue; 38 dis[v]=dis[u]+a[i^1].w; 39 if(!vis[v]){ 40 vis[v]=1; 41 q[tail++]=v; 42 } 43 } 44 } 45 return ~dis[s]; 46 } 47 int dfs(int u,int t,int limit){ 48 //cout<<"dfs "<<u<<" "<<t<<" "<<limit<<" "; 49 if(u==t||!limit) return limit; 50 int i,v,f,flow=0;vis[u]=1; 51 for(i=first[u];~i;i=a[i].next){ 52 v=a[i].to;if(vis[v]) continue; 53 if(dis[v]==dis[u]-a[i].w&&(f=dfs(v,t,min(limit,a[i].cap)))){ 54 flow+=f;limit-=f; 55 a[i].cap-=f;a[i^1].cap+=f; 56 ans+=f*a[i].w; 57 //cout<<"ans added "<<f*a[i].w<<" "; 58 if(!limit) return flow; 59 } 60 } 61 return flow; 62 } 63 int mcmf(int s,int t){ 64 int re=0,tmp; 65 while(spfa(s,t)){ 66 vis[t]=1; 67 while(vis[t]){ 68 memset(vis,0,sizeof(vis)); 69 re+=dfs(s,t,inf); 70 } 71 //cout<<"tmp re "<<re<<" "; 72 } 73 return re; 74 } 75 int main(){ 76 freopen("run.in","r",stdin); 77 freopen("run.out","w",stdout); 78 memset(first,-1,sizeof(first)); 79 int i,t1,t2,t3,t4,S,T; 80 n=read();m=read();S=1;T=n<<1; 81 for(i=2;i<n;i++) add(i,i+n,1,0); 82 add(1,n+1,inf,0);add(n,(n<<1),inf,0); 83 for(i=1;i<=m;i++){ 84 t1=read();t2=read();t3=read(); 85 add(t1+n,t2,1,t3); 86 } 87 printf("%d ",mcmf(S,T)); 88 cout<<ans<<" "; 89 }
用了某博主改进的zkw费用流，跑的好快
博主讲的也挺好的，代码注释很全，在这里转一下链接：传送门