1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
| #include <bits/stdc++.h> #define SZ(x) (int)(x).size() #define ALL(x) (x).begin(),(x).end() #define PB push_back #define EB emplace_back #define MP make_pair #define FI first #define SE second using namespace std; typedef double DB; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<PII> VPII;
const int N=5100; int k,V,m,S,T,n,s,t,d[N],cur[N]; VPII e; VI g[N]; struct Edge { int u,v,c; Edge() {} Edge(int u,int v,int c):u(u),v(v),c(c) {} }; vector<Edge> E; void init(int x) { e.clear(); for(int i=1;i<=n;i++) g[i].clear(); } void add_edge(int u,int v,int c) { e.EB(v,c); e.EB(u,0); g[u].EB(SZ(e)-2); g[v].EB(SZ(e)-1); } bool bfs() { for(int i=1;i<=n;i++) d[i]=0; queue<int> q; q.push(s); d[s]=1; while(SZ(q)) { int u=q.front(); q.pop(); for(auto x:g[u]) { int v=e[x].FI,c=e[x].SE; if(d[v]||c<=0) continue; d[v]=d[u]+1; q.push(v); } } return d[t]; } int dfs(int u,int a) { if(u==t) return a; int flow=0,f; for(int &i=cur[u];i<SZ(g[u]);i++) { int v=e[g[u][i]].FI,&c=e[g[u][i]].SE; if(d[v]!=d[u]+1||c<=0||(f=dfs(v,min(a,c)))<=0) continue; c-=f; e[g[u][i]^1].SE+=f; a-=f; flow+=f; if(!a) break; } return flow; } int dinic() { int flow=0; while(bfs()) { for(int i=1;i<=n;i++) cur[i]=0; flow+=dfs(s,0x3f3f3f3f); } return flow; } bool check(int x) { init(x); for(int i=0;i<x;i++) { for(int j=0;j<m;j++) { add_edge(E[j].u+V*i,E[j].v+V*(i+1),E[j].c); } } s=V*(x+1)+1; for(int i=0;i<x;i++) add_edge(s,S+V*i,k); ++s; add_edge(s,s-1,k); t=s+1; for(int i=0;i<=x;i++) add_edge(T+V*i,t,k); n=t; return dinic()==k; } int solve() { int l=1,r=105; while(l<r) { int mid=l+r>>1; if(check(mid)) r=mid; else l=mid+1; } return l; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>k>>V>>m>>S>>T; for(int i=1;i<=m;i++) { int u,v,c; cin>>u>>v>>c; E.EB(u,v,c); } cout<<solve()<<'\n'; return 0; }
|