BZOJ_1266.cpp

#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=505;
const int MAXM=124755*2;
const int inf=1e9;
struct Edge {
	int v, cap;
	Edge *next, *op;
	Edge(){}
	Edge(int v, int c, Edge *n):v(v), cap(c), next(n){}
}*E[MAXN];

int from[MAXM], to[MAXM], weight[MAXM], cost[MAXM], next[MAXM];
int level[MAXN], Q[MAXN], head[MAXN];
int dis1[MAXN], dis2[MAXN];
int N, M, S, T, cnt;


inline void addedge(int u, int v, int c) {
	E[u]=new Edge(v, c, E[u]); E[v]=new Edge(u, 0, E[v]);
	E[u]->op=E[v]; E[v]->op=E[u];
}

bool dinic_bfs() {
	memset(level, -1, sizeof(level));
	level[S]=0; Q[0]=S;
	for (int h=0, t=1; h<t; h++) {
		int u=Q[h], v;
		for (Edge *p=E[u]; p; p=p->next) 
			if (level[v=p->v]==-1 && p->cap>0) {
				level[v]=level[u]+1;
				Q[t++]=v;
			}
	}
	return (level[T]!=-1);
}

int dinic_dfs(int u, int low) {
	if (u==T) return low;
	int ret=0, tmp, v;
	for (Edge *p=E[u]; p && ret<low; p=p->next) 
		if (level[v=p->v]==level[u]+1 && p->cap>0) {
			if (tmp=dinic_dfs(v, min(low-ret, p->cap))) {
				ret+=tmp, p->cap-=tmp, p->op->cap+=tmp;
			}
		}
	if (!ret) level[u]=-1; return ret;
}

int dinic() {
	int maxflow=0, t;
	S=1; T=N;
	while (dinic_bfs()) {
		while (t=dinic_dfs(S, inf)) maxflow+=t;
	}
	return maxflow;
}

void spfa(int dis[], int s) {
	queue<int> Q; while (!Q.empty()) Q.pop();
	static bool vis[MAXN];
	for (int i=1; i<=N; i++) dis[i]=inf, vis[i]=false;
	dis[s]=0; vis[s]=true; Q.push(s);
	while (!Q.empty()) {
		int u=Q.front(); Q.pop(); vis[u]=false;
		for (int now=head[u]; now!=-1; now=next[now])
			if (dis[to[now]]>dis[u]+weight[now]) {
				dis[to[now]]=dis[u]+weight[now];
				if (!vis[to[now]]) {
					Q.push(to[now]); vis[to[now]]=true;
				}
			}
	}
}

void solve() {
	spfa(dis1, 1); spfa(dis2, N);
	for (int i=0; i<cnt; i++) 
		if (dis1[from[i]]+weight[i]+dis2[to[i]]==dis1[N]) 
			if (from[i]!=N && to[i]!=1) addedge(from[i], to[i], cost[i]);
	printf("%d\n%d\n", dis1[N], dinic());
}

void init() {
	memset(head, -1, sizeof(head));
	memset(E, 0, sizeof(E)); cnt=0;
}

int main() {
	scanf("%d%d", &N, &M);
	init();
	for (int i=0; i<M; i++) {
		int u, v, w, c; scanf("%d%d%d%d", &u, &v, &w, &c);
		from[cnt]=u; to[cnt]=v; weight[cnt]=w; cost[cnt]=c; next[cnt]=head[u]; head[u]=cnt++;
		from[cnt]=v; to[cnt]=u; weight[cnt]=w; cost[cnt]=c; next[cnt]=head[v]; head[v]=cnt++;
	}
	solve();
	return 0;
}