poj 1637 混合图欧拉回路学习笔记

题目大意

求混合图是否存在欧拉回路

做法

有向边我们只有增加入度出度

对于无向边，我们给它设定一个初始方向

如果不能满足|入度-出度|为偶数,无解

然后在网络流图中，

设设定方向的反向连一条边，表示反悔流量

对于最后in>out的点，最多可以提供反悔(in-out)/2点反悔流量，从源点连向它

对于out>in的点，至少接受(out-in)/2点反悔流量，连向汇点

跑一次网络流判断是否满流

由于图中一条边提供一个入度，一个出度

所以图中总入度是等于总出度的

网络流中两边流量是一样的

注意

sb我还要错多少次

网络流连边的数组还要考虑到连源点汇点的边

数组开大一点会死咩

分析

#include <cstdio>

#include <cstdio>

#include <cstring>

#include <cctype>

#include <cmath>

#include <algorithm>

using namespace std;

const int M=207;

const int S=0;

const int T=201;

const int INF=1e9;

inline int rd(){

	int x=0;bool f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(;isdigit(c);c=getchar()) x=x*10+c-48;

	return f?x:-x;

}

int tcas;

int n,m;

int in[M];

int ot[M];

int g[M],te;

struct edge{int y,f,next;}e[2407];

void addedge(int x,int y,int f){

	e[++te].y=y;e[te].f=f;e[te].next=g[x];g[x]=te;

	e[++te].y=x;e[te].f=0;e[te].next=g[y];g[y]=te;

}

int q[M],tq;

int lev[M];

bool bfs(){

	int h=0,t=1,x,p,y;

	memset(lev,-1,sizeof(lev));

	q[1]=S; lev[S]=0;

	while(h^t){

		int x=q[++h];

		for(p=g[x];p;p=e[p].next)

		if(e[p].f&&lev[y=e[p].y]==-1){

			lev[y]=lev[x]+1;

			if(y==T) return 1;

			q[++t]=y;

		}

	}

	return 0;

}

int dfs(int x,int fl){

	if(x==T) return fl;

	int p,y;

	int tp,res=0;

	for(p=g[x];p;p=e[p].next)

	if(e[p].f&&lev[x]+1==lev[y=e[p].y]){

		tp=dfs(y,min(fl,e[p].f));

		if(tp){

			e[p].f-=tp;

			e[p^1].f+=tp;

			res+=tp;

			fl-=tp;

			if(fl==0) return res;

		}

	}

	if(res==0) lev[x]=-1;

	return res;

}

int main(){

	int i,x,y,z,res;

	tcas=rd();

	while(tcas--){

		n=rd();

		m=rd();

		memset(in,0,sizeof(in));

		memset(ot,0,sizeof(ot));

		memset(g,0,sizeof(g)); te=1;

		for(i=1;i<=m;i++){

			x=rd(),y=rd(),z=rd();

			ot[x]++;

			in[y]++;

			if(z==0) addedge(y,x,1);

		}

		z=0;

		for(i=1;i<=n;i++)

			if((in[i]-ot[i])%2==1) {z=1;break;}

		if(z) puts("impossible");

		else{

			res=0;

			for(i=1;i<=n;i++){

				z=abs(in[i]-ot[i])/2;

				if(!z) continue;

				if(in[i]>ot[i]) addedge(S,i,z);

				else addedge(i,T,z),res+=z;

			}

			while(bfs()) res-=dfs(S,INF);

			if(res>0) puts("impossible");

			else puts("possible");

		}

	}

	return 0;

}

巴特西

poj 1637 混合图欧拉回路学习笔记

题目大意

做法

注意

分析

最新文章

热门文章

巴特西

poj 1637 混合图欧拉回路 学习笔记

题目大意

做法

注意

分析

最新文章

热门文章

poj 1637 混合图欧拉回路学习笔记