luogu P3305 [SDOI2013]费用流

题目链接

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;

}

巴特西

luogu P3305 [SDOI2013]费用流

题目链接

题解

代码

最新文章

热门文章