题目链接
bz似乎挂了...luogu P3305 [SDOI2013]费用流
题解
dalao告诉我，这题 似乎很水.... 懂了题目大意就可以随便切了 问1，最大流 问2，二分最大边权求，check是否为最大流 PS：今天代码很多bug....惨orz
代码
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x7fffffff
#define eps 1e-4
const int maxn = 5007;
using std::queue;
using std::min;
int n,m,S,T;
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9') {if(f == '-') f = -1;c = getchar();}
while(c <= '9'&&c >= '0') x = x * 10 + c - '0',c = getchar();
return x*f;
}
struct node{
int v;double flow;int next;
}edge[maxn<<2];
int head[maxn],num=1;
inline void add_edge(int u,int v,double flow) { edge[++num].v = v;edge[num].flow = flow;edge[num].next = head[u];head[u] = num; }
inline void ADD (int u,int v,double flow) {
add_edge(u,v,flow);
add_edge(v,u,0);
}
int a[maxn],b[maxn];double c[maxn];int lev[maxn],cur[maxn];
bool bfs() {
for(int i = 0;i <= n;++ i) lev[i] = -1,cur[i] = head[i];
queue<int>q;q.push(S),lev[S] = 0;
while(!q.empty()) {
int u = q.front();q.pop();
for(int i = head[u];i;i = edge[i].next) {
int v = edge[i].v;
if(lev[v] == -1&&edge[i].flow > 0)
lev[v] = lev[u]+1,q.push(v);
}
}
if(lev[T] != -1)return true;
return false;
}
double dfs(int x,double flow) {
if(x == T)return flow;
double delta,rest = 0;
for(int v,&i = cur[x];i;i = edge[i].next) {
v = edge[i].v;
if(lev[v] == lev[x]+1&&edge[i].flow > 0) {
delta = dfs(v,std::min(flow - rest,edge[i].flow));
if(delta) {
edge[i].flow -= delta;
edge[i^1].flow += delta;
rest+=delta;if(rest == delta)break;
}
}
}
if(rest==flow) lev[x]=-1;
return rest;
}
double Dinic() {
double ret = 0;
while(bfs())
ret += dfs(S,INF);
return ret;
}
void rebuild(double mid) {
memset(head,0,sizeof head);
num=1;
for(int i = 1;i <= m;++ i) {
ADD(a[i],b[i],min(mid,c[i]));
}
}
int main() {
double p;
n = read(),m = read(),scanf("%lf",&p);
S=1;T=n;
for (int i = 1;i <= m;++ i) scanf("%d%d%lf",&a[i],&b[i],&c[i]), ADD(a[i],b[i],c[i]);
double Max_flow;
Max_flow = Dinic();
printf("%.0lf\n",Max_flow);
double l = 0,r = 1000000086.0;
while (r - l > eps) {
double mid = (l + r) / 2;
rebuild(mid);
if(Dinic() != Max_flow) l = mid;
else r = mid;
}
printf("%.4lf\n",l*p);
return 0;
}
转载于:https://www.cnblogs.com/sssy/p/8660479.html
相关资源：锣鼓声声迎新春——新年工作计划ppt模板.zip
