【[SDOI2009]晨跑】

板子

题意就是每个点只能经过一次

所以非常显然拆点，除去\(1,n\)每个点\(i\)向\(i'\)连一条容量为\(1\)费用为\(0\)的边

剩下的边按照输入给出的建就好了

代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#define maxn 405

#define re register

#define LL long long

#define inf 999999999

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

struct E{int v,nxt,f,w;}e[60005];

int head[maxn],d[maxn],vis[maxn];

int n,m,num=1,S,T;

inline void add(int x,int y,int ca,int z){e[++num].v=y;e[num].nxt=head[x],e[num].w=z;e[num].f=ca;head[x]=num;}

inline void C(int x,int y,int ca,int z){add(x,y,ca,z),add(y,x,0,-z);}

inline int SPFA()

{

	std::queue<int> q;

	for(re int i=S;i<=T;i++) d[i]=inf,vis[i]=0;

	q.push(T),vis[T]=0,d[T]=0;

	while(!q.empty())

	{

		int k=q.front();q.pop();vis[k]=0;

		for(re int i=head[k];i;i=e[i].nxt)

		if(e[i^1].f&&d[e[i].v]>d[k]+e[i^1].w)

		{

			d[e[i].v]=d[k]+e[i^1].w;

			if(!vis[e[i].v]) q.push(e[i].v),vis[e[i].v]=1;

		}

	}

	return d[S]<inf;

}

int dfs(int x,int now)

{

	if(x==T||!now) return now;

	int flow=0,ff;vis[x]=1;

	for(re int i=head[x];i;i=e[i].nxt)

	if(e[i].f&&!vis[e[i].v]&&d[x]+e[i^1].w==d[e[i].v])

	{

		ff=dfs(e[i].v,min(e[i].f,now));

		if(ff<=0) continue;

		now-=ff,flow+=ff;

		e[i].f-=ff,e[i^1].f+=ff;

		if(!now) break;

	}

	return flow;

}

int main()

{

	n=read(),m=read();C(1,n+1,inf,0),C(n,n+n,inf,0);

	for(re int i=2;i<n;i++) C(i,i+n,1,0);

	S=1,T=n+n;

	int x,y,z;

	for(re int i=1;i<=m;i++) x=read(),y=read(),z=read(),C(x+n,y,1,z);

	int tot=0,ans=0;

	while(SPFA())

	{

		vis[T]=1;

		while(vis[T])

		{

			for(re int i=S;i<=T;i++) vis[i]=0;

			int F=dfs(S,inf);

			tot+=F,ans+=F*d[S];

		}

	}

	printf("%d %d\n",tot,ans);

	return 0;

}

巴特西

【[SDOI2009]晨跑】

最新文章

热门文章