思路:如果一个DAG要的路径上只要一条边去切掉，那么要怎么求？很容易就想到最小割，但是如果直接做最小割会走出重复的部分，那我们就这样:反向边设为inf，这样最小割的时候就不会割到了，判断无解我们直接用tarjan
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #define ll long long 7 const ll inf = 1ll << 60; 8 struct edge{ 9 int u,v,w; 10 }e[200005]; 11 ll flow[200005]; 12 int op[200005],dis[200005],cnt[200005],a[115][115],pd[10005]; 13 int tot,go[200005],next[200005],first[200005],S,T,nodes,sz; 14 int n,m,vis[200005],instack[200005],c[200005],top,dfn[200005],low[200005],belong[200005],num; 15 int read(){ 16 int t=0,f=1;char ch=getchar(); 17 while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();} 18 while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} 19 return t*f; 20 } 21 void insert(int x,int y){ 22 tot++; 23 go[tot]=y; 24 next[tot]=first[x]; 25 first[x]=tot; 26 } 27 void insert(int x,int y,ll z){ 28 tot++; 29 go[tot]=y; 30 next[tot]=first[x]; 31 first[x]=tot; 32 flow[tot]=z; 33 } 34 void add(int x,int y,ll z){ 35 insert(x,y,z);op[tot]=tot-1; 36 insert(y,x,inf);op[tot]=tot+1; 37 } 38 void tarjan(int x){ 39 vis[x]=instack[x]=1; 40 c[++top]=x;dfn[x]=low[x]=++sz; 41 for (int i=first[x];i;i=next[i]){ 42 int pur=go[i]; 43 if (!vis[pur]){ 44 tarjan(pur); 45 low[x]=std::min(low[x],low[pur]); 46 }else if (instack[pur]){ 47 low[x]=std::min(low[x],dfn[pur]); 48 } 49 } 50 if (low[x]==dfn[x]){ 51 num++; 52 while (c[top]!=x){ 53 belong[c[top]]=num; 54 instack[c[top]]=0; 55 top--; 56 } 57 belong[c[top]]=num; 58 instack[c[top]]=0; 59 top--; 60 } 61 } 62 ll dfs(int x,ll f){ 63 if (x==T) return f; 64 int mn=nodes;ll sum=0; 65 for (int i=first[x];i;i=next[i]){ 66 int pur=go[i]; 67 if (flow[i]&&dis[pur]+1==dis[x]){ 68 ll F=std::min(f-sum,flow[i]); 69 ll save=dfs(pur,F); 70 flow[i]-=save; 71 flow[op[i]]+=save; 72 sum+=save; 73 if (dis[S]>=nodes||f==sum) return sum; 74 } 75 if (flow[i]) mn=std::min(mn,dis[pur]); 76 } 77 if (sum==0){ 78 cnt[dis[x]]--; 79 if (cnt[dis[x]]==0){ 80 dis[S]=nodes; 81 }else{ 82 dis[x]=mn+1; 83 cnt[dis[x]]++; 84 } 85 } 86 return sum; 87 } 88 int main(){ 89 n=read();m=read(); 90 for (int i=1;i<=m;i++){ 91 e[i].u=read()+1,e[i].v=read()+1,e[i].w=read(); 92 a[e[i].u][e[i].v]=1; 93 insert(e[i].u,e[i].v); 94 } 95 for (int i=1;i<=n;i++) 96 if (!vis[i]) tarjan(i); 97 if (belong[1]==belong[n]){ 98 puts("-1"); 99 return 0; 100 } 101 for (int i=1;i<=n;i++) 102 a[i][i]=1; 103 for (int k=1;k<=n;k++) 104 for (int i=1;i<=n;i++) 105 for (int j=1;j<=n;j++) 106 a[i][j]|=a[i][k]&&a[k][j]; 107 for (int i=1;i<=n;i++) 108 if (a[1][i]&&a[i][n]) pd[i]=1; 109 for (int i=1;i<=m;i++) 110 if (pd[e[i].u]&&pd[e[i].v]) 111 add(e[i].u,e[i].v,e[i].w); 112 S=1;T=n;nodes=n; 113 int ans=0; 114 while (dis[S]<nodes&&ans<inf) ans+=dfs(S,inf); 115 if (ans==0) printf("-1"); 116 else printf("%d\n",ans); 117 }