lp2153 SDOI2009 晨跑

题意简述：求一张图上不共点两点间最大路径数。
首先考虑不共边最大路径数，很容易可以想到大力上一个最大流，边流量为一。
然后考虑不共点最大路径数。我们发现，可以通过拆点来构成约束条件。具体来说就是将每个点拆成入点和出点，然后跑一个网络流。
现在还要求一个最短总路径长度，很容易可以想到费用流。具体来说，就将每一条边的费用设置为它的长度。然后跑一遍即可。

#include<iostream>
#include<cstdio>
#include<queue>

const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[100005];
int h[405],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);
	Eadd(V,U,0,-C);
}

int n,m,s,t,dis[405],val[405],fa[405],nw[405];
bool vis[405];
std::queue<int> q;
inline int spfa(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	vis[s]=1,dis[s]=0,fa[t]=-1;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(val[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;
}

void init(){
	scanf("%d%d",&n,&m);
	s=1,t=2*n;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int u,v,c;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&u,&v,&c);
		add(n+u,v,1,c);
	}
	for(int i=2;i<n;++i){
		add(i,n+i,1,0);
	}
	add(1,n+1,1926,0);
	add(n,2*n,1926,0);
	int ansW=0,ansC=0,p;
	while(spfa()){
		p=t;
		ansW+=val[t];
		ansC+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
	printf("%d %d\n",ansW,ansC);
}

int main(){
	init();
	return 0;
}