提出 #579289

---

ソースコード 拡げる

#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

static const auto VMAX = 200;
static const auto INF = 1000000000;

typedef int w_t;
struct EDGE {
	int v; w_t c; int i;
	EDGE(int v,w_t c,int i):v(v),c(c),i(i) {}
};
namespace Network
{

	int V,S,T;//TODO
	vector<EDGE> f[VMAX];
	int d[VMAX];
	static int i[VMAX];

	static w_t push(int u,w_t r)
	{
		if(u==T)return r;
		const w_t o=r;
		for(;i[u]!=f[u].size();i[u]++)
		{
			if(f[u][i[u]].c==0)continue;
			const int v=f[u][i[u]].v;
			if(d[v]!=d[u]+1||i[v]==f[v].size())continue;
			const w_t w=push(v,min(r,f[u][i[u]].c));
			if(w==0)continue;
			f[u][i[u]].c-=w;
			f[v][f[u][i[u]].i].c+=w;
			if((r-=w)==0)break;
		}
		return o-r;
	}

	static bool bfs()
	{
		int qh=0,qt=0;
		memset(d,0xFF,V*sizeof(int));
		d[S]=0;i[qt++]=S;
		do
		{
			const int u=i[qh++];
			vector<EDGE>::const_iterator it;
			for(it=f[u].begin();it!=f[u].end();++it)
			{
				if(it->c==0||d[it->v]>=0)continue;
				d[it->v]=d[u]+1;
				if(it->v==T)return true;
				i[qt++]=it->v;
			}
		} while(qh!=qt);
		return false;
	}

	w_t flow()
	{
		w_t ret=0;
		while(bfs())
		{
			memset(i,0x00,V*sizeof(int));
			ret+=push(S,INF);
		}
		return ret;
	}

	inline void insert(int a,int b,w_t cab,w_t cba)
	{
		f[a].push_back(EDGE(b,cab,f[b].size()  ));
		f[b].push_back(EDGE(a,cba,f[a].size()-1));
	}

	void clear()
	{
		for(int i=0;i<V;i++)vector<EDGE>().swap(f[i]);
	}
}

static int &V = Network::V, B, &S = Network::S, &T = Network::T;
static int D[VMAX];

struct CDE {
	int v, c, d; bool i;
	CDE(int v, int c, int d) : v(v), c(c), d(d) {}
};

static vector<CDE> E[VMAX];
static bool R[VMAX];

static void dfs(int u) {
	R[u] = true;
	for(auto &e : Network::f[u]) if(e.c != 0 && !R[e.v]) dfs(e.v);
}

static void dfs() {
	fill(R, R + V, false);
	dfs(S);
}

static void Dijkstra(bool ig) {
	static bool F[VMAX];
	fill(D, D + V, INF);
	fill(F, F + V, false);
	D[S] = 0;
	for(; ; ) {
		auto u = -1;
		for(auto i = 0; i < V; i++) {
			if(!F[i] && D[i] != INF && (u < 0 || D[i] < D[u])) u = i;
		}
		if(u < 0) break;
		F[u] = true;
		for(auto &cde : E[u]) {
			if(ig && cde.i) continue;
			if(D[u] + cde.d < D[cde.v]) D[cde.v] = D[u] + cde.d;
		}
	}
}

static double solve() {
	for(; ; ) {
//printf("B = %d\n", B);
		Dijkstra(false);
		auto d1 = D[T];
//printf("d1 = %d\n", d1);
		if(B == 0) return d1;
		for(auto u = 0; u < V; u++) {
			for(auto &cde : E[u]) {
				if(D[u] + cde.d == D[cde.v]) {
					Network::insert(u, cde.v, cde.c, 0);
				}
			}
		}
		auto f = Network::flow();
//printf("f = %d\n", f);
		dfs();
		Network::clear();
		for(auto u = 0; u < V; u++) {
			for(auto &cde : E[u]) cde.i = R[u] && !R[cde.v] && D[u] + cde.d == D[cde.v];
//for(auto &cde : E[u]) if(cde.i) printf("%d->%d (c=%d d=%d) in cut\n", u + 1, cde.v + 1, cde.c, cde.d);
		}
		Dijkstra(true);
		auto d2 = D[T];
//printf("d2 = %d\n", d2);
		if(d2 == INF || (B + (f - 1) / f) <= d2 - d1) return d1 + (double)B / f;
		B -= (d2 - d1) * f;
		for(auto u = 0; u < V; u++) {
			for(auto &cde : E[u]) if(cde.i) cde.d += d2 - d1;
		}
	}
}

static void input() {
	int m;
	scanf("%d%d%d%d%d", &V, &m, &B, &S, &T); S--; T--;
	while(--m >= 0) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &d, &c); a--; b--;
		E[a].emplace_back(b, c, d);
	}
}

int main() {
	input();
	printf("%.15f\n", solve());
	return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘void input()’:
./Main.cpp:160:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d", &V, &m, &B, &S, &T); S--; T--;
                                         ^
./Main.cpp:163:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &a, &b, &d, &c); a--; b--;
                                    ^

ジャッジ結果