bzoj
sol
每天每座城市建一个点，该怎么连边就怎么连边，每次只需要在上一次的残余网络上跑最大流，所以复杂度不会太高。
code
#include<cstdio>#include<algorithm>#include<cstring>#include<queue>using namespace std;int gi(){ ???int x=0,w=1;char ch=getchar(); ???while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); ???if (ch=='-') w=0,ch=getchar(); ???while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); ???return w?x:-x;}const int N = 1e5+5;const int inf = 1e9;struct edge{int to,nxt,w;}a[N<<5];int n,m,num,uu[N],vv[N],ww[N],id[51][2018],tot,S,T,head[N],cnt=1,dep[N],cur[N],flow,ans;queue<int>Q;void link(int u,int v,int w){ ???a[++cnt]=(edge){v,head[u],w}; ???head[u]=cnt; ???a[++cnt]=(edge){u,head[v],0}; ???head[v]=cnt;}bool bfs(){ ???memset(dep,0,sizeof(dep)); ???dep[S]=1;Q.push(S); ???while (!Q.empty()) ???{ ???????int u=Q.front();Q.pop(); ???????for (int e=head[u];e;e=a[e].nxt) ???????????if (a[e].w&&!dep[a[e].to]) ???????????????dep[a[e].to]=dep[u]+1,Q.push(a[e].to); ???} ???return dep[T];}int dfs(int u,int f){ ???if (u==T) return f; ???for (int &e=cur[u];e;e=a[e].nxt) ???????if (a[e].w&&dep[a[e].to]==dep[u]+1) ???????{ ???????????int tmp=dfs(a[e].to,min(a[e].w,f)); ???????????if (tmp) {a[e].w-=tmp;a[e^1].w+=tmp;return tmp;} ???????} ???return 0;}int Dinic(){ ???int res=0; ???while (bfs()) ???{ ???????for (int i=1;i<=tot;++i) cur[i]=head[i]; ???????while (int tmp=dfs(S,inf)) res+=tmp; ???} ???return res;}int main(){ ???n=gi();m=gi();num=gi(); ???for (int i=1;i<=m;++i) uu[i]=gi(),vv[i]=gi(),ww[i]=gi(); ???S=++tot;T=++tot; ???for (int i=1;i<=n;++i) id[i][0]=++tot; ???link(S,id[1][0],num); ???while (++ans) ???{ ???????for (int i=1;i<=n;++i) id[i][ans]=++tot,link(id[i][ans-1],id[i][ans],inf); ???????for (int i=1;i<=m;++i) link(id[uu[i]][ans-1],id[vv[i]][ans],ww[i]); ???????link(id[n][ans],T,num);flow+=Dinic();if (flow==num) break; ???} ???printf("%d\n",ans);return 0;}