萌新求助图论小水题
查看原帖
萌新求助图论小水题
209454
watermonster楼主2020/10/6 13:50

RT,为什么我会TLE爆零而别人的代码都跑得飞快?

代码:

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>

using namespace std;

#define re register
#define il inline

const int N=210;
const int M=40010;
const int inf=0x3f3f3f3f;

namespace IO
{
char bufr[(1<<21)+100],bufw[(1<<21)+100],*p1=bufr,*p2=bufr,Tmp[100];
int p,p3=-1;
il char get_char(){return p1==p2&&(p2=(p1=bufr)+fread(bufr,1,1<<21,stdin))?EOF:*p1++;}
#define isdigit(ch) (ch>=48&&ch<=57)
template <typename T>
il void read(T &x)
{
	x=0;re char ch=get_char();
	while(!isdigit(ch)) ch=get_char();
	while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=get_char();
}
template <typename T>
il void write(T x)
{
	if(x/10) write(x/10);
	putchar(x%10+48);
}
}
using namespace IO;

il void swap(int &a,int &b){a^=b^=a^=b;}
il int min(int a,int b){return a<b?a:b;}

int T,n;

namespace dinic
{
	int cnt=1,h[N];
	struct edge{int v,res,nxt;}e[M];
	il void add(int u,int v,int w){e[++cnt]=(edge){v,w,h[u]};h[u]=cnt;}
	int dep[N],cur[N];
	il bool bfs(int s,int t)
	{
		for(re int i=1;i<=n;++i)
			dep[i]=0,cur[i]=h[i];
		queue<int>q;q.push(s);dep[s]=1;
		while(!q.empty())
		{
			re int u=q.front();q.pop();
			for(re int i=h[u];i;i=e[i].nxt)
				if(!dep[e[i].v]&&e[i].res)
				{
					dep[e[i].v]=dep[u]+1;
					q.push(e[i].v);
				}
		}
		return dep[t];
	}
	il int dfs(int x,int flow,int t)
	{
		if(!flow||x==t) return flow;
		re int tmp=0,f;
		for(re int i=cur[x];i;i=e[i].nxt)
		{
			cur[x]=i;
			if(dep[e[i].v]>dep[x]&&(f=dfs(e[i].v,min(e[i].res,flow-tmp),t)))
			{
				e[i].res-=f;e[i^1].res+=f;
				tmp+=f;
				if(!(flow-tmp)) break;
			}
		}
		return tmp;
	}
	il int maxflow(int s,int t)
	{
		for(re int i=2;i<=cnt;i+=2)
			e[i].res+=e[i^1].res,e[i^1].res=0;
		re int ans=0;
		while(bfs(s,t)) ans+=dfs(s,inf,t);
		return ans;
	}
}

namespace GHT
{
	int cnt,h[N],lg;
	struct edge{int v,w,nxt;}e[M];
	il void add(int u,int v,int w){e[++cnt]=(edge){v,w,h[u]};h[u]=cnt;}
	int node[N],tmp1[N],tmp2[N];
	il void build(int l,int r)
	{
		if(l>=r) return;
		re int u=node[l],v=node[l+1];
		re int cut=dinic::maxflow(u,v);
		add(u,v,cut);add(v,u,cut);
		re int cnt1=0,cnt2=0;
		for(re int i=l;i<=r;++i)
		{
			if(dinic::dep[node[i]]) tmp1[++cnt1]=node[i];
			else tmp2[++cnt2]=node[i];
		}
		for(re int i=l;i<=l+cnt1-1;++i) node[i]=tmp1[i-l+1];
        for(re int i=l+cnt1;i<=r;++i) node[i]=tmp2[i-cnt1-l+1];
		build(l,l+cnt1-1);build(l+cnt1,r);
	}
	int dep[N],fa[10][N],st[10][N];
	il void dfs(int x,int f)
	{
		dep[x]=dep[f]+1;
		for(re int i=1;i<=lg;++i)
		{
			fa[i][x]=fa[i-1][fa[i-1][x]];
			st[i][x]=min(st[i-1][x],st[i-1][fa[i-1][x]]);
		}
		for(re int i=h[x];i;i=e[i].nxt)
			if(e[i].v^f)
			{
				st[0][e[i].v]=e[i].w;
				fa[0][e[i].v]=x;
				dfs(e[i].v,x);
			}
	}
	il int query(int u,int v)
	{
		re int res=inf;
		if(dep[u]<dep[v]) swap(u,v);
		for(re int i=lg;i>=0;--i)
			if(dep[fa[i][u]]>=dep[v])
				res=min(res,st[i][u]),u=fa[i][u];
		if(u==v) return res;
		for(re int i=lg;i>=0;--i)
			if(fa[i][u]^fa[i][v])
			{
				res=min(res,st[i][u]);
				res=min(res,st[i][v]);
				u=fa[i][u];v=fa[i][v];
			}
		res=min(res,st[0][u]);
		res=min(res,st[0][v]);
		return res;
	}
}

il void init()
{
	dinic::cnt=1;GHT::cnt=0;
	memset(dinic::h,0,sizeof(dinic::h));
	memset(GHT::h,0,sizeof(GHT::h));
	memset(GHT::st,0x3f,sizeof(GHT::st));
	for(re int i=1;i<=n;++i) GHT::node[i]=i;
}

int main()
{
	read(T);
	for(re int Cas=1;Cas<=T;++Cas)
	{
		read(n);init();GHT::lg=log2(n);
		for(re int i=1;i<=n;++i)
			for(re int j=1,w;j<=n;++j)
			{
				read(w);
				if(!w) continue;
				dinic::add(i,j,w);
				dinic::add(j,i,0);
			}
		GHT::build(1,n);GHT::dfs(1,0);
		printf("Case #%d:\n",Cas);
		for(re int i=1;i<=n;++i)
			for(re int j=1;j<=n;++j)
			{
				write(i^j?GHT::query(i,j):0);
				putchar(j<n?' ':'\n');
			}
	}
	return 0;
}
2020/10/6 13:50
加载中...