思路：

呃 ?水題不解釋 行么,,

//By SiriusRen #include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define mem(x,y) memset(x,y,sizeof(x)) const int N=88888,M=444; int n,m,xx,yy,zz,edge[N],cost[N],v[N],next[N],first[M]; int with[M],vis[M],minn[M],dis[M],tot,ans1,ans2; void Add(int x,int y,int C,int E){edge[tot]=E,cost[tot]=C,v[tot]=y,next[tot]=first[x],first[x]=tot++;} void add(int x,int y,int C,int E){Add(x,y,C,E),Add(y,x,-C,0);} bool tell(){mem(vis,0),mem(minn,0x3f),mem(dis,0x3f);queue<int>q;q.push(1),dis[1]=0;while(!q.empty()){int t=q.front();q.pop(),vis[t]=0;for(int i=first[t];~i;i=next[i])if(dis[v[i]]>dis[t]+cost[i]&&edge[i]){dis[v[i]]=dis[t]+cost[i],minn[v[i]]=min(minn[t],edge[i]),with[v[i]]=i;if(!vis[v[i]])vis[v[i]]=1,q.push(v[i]);}}return dis[n*2]!=0x3f3f3f3f; } void zeng(){for(int i=2*n;i^1;i=v[with[i]^1])edge[with[i]]-=minn[n*2],edge[with[i]^1]+=minn[n*2];ans1+=minn[n*2],ans2+=dis[n*2]*minn[n*2]; } int main(){mem(first,-1),scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&xx,&yy,&zz);add(xx+n,yy,zz,1);}for(int i=2;i<n;i++)add(i,i+n,0,1);add(1,n+1,0,M),add(n,2*n,0,M);while(tell())zeng();printf("%d %d\n",ans1,ans2); }

?

轉載于:https://www.cnblogs.com/SiriusRen/p/6637680.html

總結

以上是生活随笔為你收集整理的BZOJ 1877 拆点费用流的全部內容，希望文章能夠幫你解決所遇到的問題。

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