转自老blog
首先说一下 这个题其实就是最大流 只有最大流才可能是答案
费用一定会加在最大流上最大边的 因此二分
#include<iostream> #include<algorithm> #include<cstdlib> #include<cmath> #include<queue> #include<vector> #include<cstring> #include<stack> using namespace std; double eps=1e-6; const int INF = 0x7f7f7f7f; struct edge { int from,to,pre;double cap,flow; }Edge[2500]; struct edg { int from,to;double cap,flow; }road[2500]; int cur[200];//当前弧优化 int head[200]; int s,t,n,m,p; inline int init() { int now=0;char c;bool flag=false;int ju=1; while(1) { c=getchar(); if(c=='-') { ju=-1; } else if(c>='0'&&c<='9') { now=now*10+c-'0'; flag=true; } else if(flag)return now*ju; } } int cnt=0; inline void addedge(int from,int to,double cap) { Edge[++cnt]=((edge){from,to,head[from],cap,0.0}); head[from]=cnt; Edge[++cnt]=((edge){to,from,head[to],0.0,0.0}); head[to]=cnt; } int dis[150]; bool vis[150]; queue<int> q; bool bfs() { int now; while(!q.empty())q.pop(); memset(vis,false,sizeof(vis)); vis[s]=true;dis[s]=0;q.push(s); while(!q.empty()) { now=q.front();q.pop(); for(int j=head[now];j;j=Edge[j].pre) { if(!vis[Edge[j].to]&&Edge[j].cap>Edge[j].flow) { dis[Edge[j].to]=dis[now]+1; vis[Edge[j].to]=true; q.push(Edge[j].to); if(Edge[j].to==t)return 1; } } } return 0; } double dfs(int now,double maxflow) { if(now==t||maxflow==0)return maxflow; int &j=cur[now]; double flow=0.0,f;//可以认为flow是当前节点的总流 f是层流 for(;j;j=Edge[j].pre) { if(dis[Edge[j].to]==dis[now]+1&&(f=dfs(Edge[j].to,min(maxflow,Edge[j].cap-Edge[j].flow)))>0) { flow+=f; Edge[j].flow+=f; Edge[((j-1)^1)+1].flow-=f; maxflow-=f; if(maxflow==0.0)break; } } return flow; } double dinic() { double tot=0.0; while(bfs()) { for(int i=s;i<=t;i++) { cur[i]=head[i]; } tot+=dfs(s,INF*1.0); } return tot; } void make(double mid) { cnt=0; memset(head,0,sizeof(head)); for(int i=1;i<=m;i++) { addedge(road[i].from,road[i].to,min(road[i].cap,mid)); } return; } int main() { double l=1,mid; s=1; double r; n=init();m=init();p=init(); t=n; int a,b,c; for(int i=1;i<=m;i++) { a=init();b=init();c=init();addedge(a,b,c*1.0); road[i].from=a;road[i].to=b;road[i].cap=c;road[i].flow=0.0; r=max(r,c*1.0); } double tmp; double ans=dinic(); while(r-l>eps) { mid=(l+r)/2; make(mid); tmp=dinic(); if(ans-tmp<eps) { r=mid; } else l=mid; } printf("%.0f %.4f ",ans,l*p); return 0; }