qwq
首先，我們觀察到題目中提到的每天只能乘坐一次航班的限制，很容易想到建分層圖，也就是通過枚舉天數，然后每天加入一層新的點。
（然而我一開始想的卻是erf）

考慮從小到大枚舉天數，然后每次新建一層。

首先我們先讓\(S->第0層的對應的起始節點\)，流量為初始人數的邊

然后相鄰兩層之間，若存在航班，則兩個之間連流量為次數的邊。
對應節點之間連\(inf\)的邊，表示可以待在原地。

然后每一層的結束節點，都向T連邊，表示每一天都可以有人到達終止節點。

然后直接跑最大流，假設初始人數是\(k\),每次讓\(k-=maxflow\)

直到\(k=0\)，輸出對應的天數即可

// luogu-judger-enable-o2 #include<bits/stdc++.h> #define mk make_pair #define pb push_back #define ll long longusing namespace std;inline int read() {int x=0,f=1;char ch=getchar();while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f; }const int maxn = 10010; const int maxm = 2e6+1e2; const int inf = 1e9;int point[maxn],nxt[maxm],to[maxm],val[maxm]; int cnt=1,n,m; int h[maxn];void addedge(int x,int y,int w) {nxt[++cnt]=point[x];to[cnt]=y;val[cnt]=w;point[x]=cnt; }void insert(int x,int y,int w) {addedge(x,y,w);addedge(y,x,0); }int s,t; queue<int> q;bool bfs(int s) {memset(h,-1,sizeof(h));h[s]=0;q.push(s);while (!q.empty()){int x= q.front();q.pop();for (int i=point[x];i;i=nxt[i]){int p=to[i];if (h[p]==-1 && val[i]>0){h[p]=h[x]+1;q.push(p);}}}if (h[t]==-1) return false;return true; }int dfs(int x,int low) {if (x==t || low==0) return low;int totflow=0;for (int i=point[x];i;i=nxt[i]){int p = to[i];if(h[p]==h[x]+1 && val[i]>0){int tmp = dfs(p,min(low,val[i]));\val[i]-=tmp;val[i^1]+=tmp;low-=tmp;totflow+=tmp;if(low==0) return totflow;}}if(low>0) h[x]=-1;return totflow; } int dinic() {int ans=0;while (bfs(s)){ans=ans+dfs(s,inf);}return ans; }int x[maxm],y[maxm],w[maxm]; int k;int main() {s=maxn-10;t=s+1;n=read(),m=read(),k=read();for (int i=1;i<=m;i++){x[i]=read(),y[i]=read(),w[i]=read();}insert(s,1,k);insert(n,t,k);//dinic();int ansflow=k;ansflow-=dinic();for (int i=1;i<=1000000;i++){for(int j=1;j<=m;j++) insert(x[j]+(i-1)*n,y[j]+i*n,w[j]);for(int j=1;j<=n;j++) insert(j+(i-1)*n,j+i*n,inf);insert(n+i*n,t,k);ansflow-=dinic();if(!ansflow) {cout<<i<<endl;return 0;} //cout<<i<<" "<<ansflow<<endl;}return 0; }

轉載于:https://www.cnblogs.com/yimmortal/p/10163265.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的洛谷4400 BlueMary的旅行（分层图+最大流）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。