【網絡流】Modular Production Line

焦作上的一道，網絡流24題中的原題....

• https://nanti.jisuanke.com/t/31715
  給出了1e5個點，但是因為最多200條邊，也就是最多用到400個點，所用先離散化，然后建圖。
  建圖：
  1.對權值為w的區間[u,v],加邊id(u)->id(v+1),容量為1,費用為-w;
  2.對所有相鄰的點加邊id(i)->id(i+1),容量為正無窮,費用為0;
  3.建立源點匯點,由源點s向最左側的點加邊,容量為K,費用為0,由最右側的點向匯點加邊,容量為K,費用為0
  4.跑出最大流后,最小費用取絕對值就是能獲得的最大權

離散化那里不太熟
spfa的slf優化能快200ms

#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=10010; const int maxm=100010; const int inf=0x3f3f3f3f; struct edge{int to,next,cap,flow,cost; }e[maxm]; int head[maxn],tol,cost; int pre[maxn],dis[maxn]; bool vis[maxn]; int N; void init(int n){N=n;tol=1;cost=0;memset(head,0,sizeof(head)); } void addedge(int u,int v,int cap,int cost){++tol;e[tol].to=v;e[tol].next=head[u];e[tol].cap=cap;e[tol].cost=cost;e[tol].flow=0;head[u]=tol;++tol;e[tol].to=u;e[tol].next=head[v];e[tol].cap=0;e[tol].flow=0;e[tol].cost=-cost;head[v]=tol; } bool spfa(int s,int t){deque<int>q;for (int i = 0; i <=N ; ++i) {dis[i]=inf;vis[i]=false;pre[i]=-1;}dis[s]=0;vis[s]=true;q.push_front(s);while (!q.empty()){int u=q.front();q.pop_front();vis[u]=0;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(e[i].cap>e[i].flow&&dis[v]>dis[u]+e[i].cost){dis[v]=dis[u]+e[i].cost;pre[v]=i;if(!vis[v]){vis[v]=true;if(!q.empty()){if(dis[v]<dis[q.front()]) q.push_front(v);else q.push_back(v);}else q.push_back(v);}}}}if(pre[t]==-1) return false;else return true; } int mcfc(int s,int t){int flow=0;while (spfa(s,t)){int minn=inf;for(int i=pre[t];i!=-1;i=pre[e[i^1].to]){if(minn>e[i].cap-e[i].flow){minn=e[i].cap-e[i].flow;}}for(int i=pre[t];i!=-1;i=pre[e[i^1].to]){e[i].flow+=minn;e[i^1].flow-=minn;cost+=e[i].cost*minn;}flow+=minn;}return flow; } struct node{int a,b,c; }f[300]; map<int,int>mp; int main(){int T;scanf("%d",&T);int n,m,k,cnt;int a,b,w;while (T--){scanf("%d%d%d",&n,&m,&k);cnt=0;mp.clear();for (int i = 1; i <= k; ++i) {scanf("%d%d%d",&a,&b,&w);f[i]=node{a,b+1,w};mp[a]=mp[b+1]=1;}map<int,int>::iterator it;for(it=mp.begin();it!=mp.end();it++){int id=it->first;mp[id]=++cnt;}init(cnt+5);int s=0,t=cnt+1;addedge(0,1,m,0);addedge(cnt,t,m,0);for (int i = 1; i <cnt ; ++i) {addedge(i,i+1,inf,0);}for (int j = 1; j <=k ; ++j) {addedge(mp[f[j].a],mp[f[j].b],1,-f[j].c);}mcfc(s,t);printf("%d\n",-cost);} }

轉載于:https://www.cnblogs.com/smallocean/p/9685916.html

總結

以上是生活随笔為你收集整理的【网络流】Modular Production Line的全部內容，希望文章能夠幫你解決所遇到的問題。

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