dinic不懂为什么TLE了,求救
查看原帖
dinic不懂为什么TLE了,求救
1381901
Starpop楼主2024/11/25 07:41
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=101100;

inline int read()
{
	int f=1,x=0; char ch=getchar();
	while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }
	while(isdigit(ch))  { x=x*10+ch-'0';    ch=getchar(); }
	return f*x;
}

struct edge
{ int next,to,val; };
int n1,n2,n3,s,t;
int head[N],tot;
int cur[N],lv[N];
edge e[N<<1];

inline void add_edge(int from,int to,int val)
{
    e[tot].next=head[from];
    e[tot].to=to;
    e[tot].val=val;
    head[from]=tot++;
}

inline void DoubleEdge(int u,int v,int w)
{
    add_edge(u,v,w);
    add_edge(v,u,0);
}

inline bool level(int s,int t)
{
	memset(lv,0,sizeof(lv)); lv[s]=1;
	memcpy(cur,head,sizeof(head)); cur[s]=head[s];
	queue<int> q; q.push(s);
	while(!q.empty())
	{
		int u=q.front(); q.pop();
		if(u==t) return true;
		for(int i=head[u];~i;i=e[i].next)
		{
			int v=e[i].to;
			if(e[i].val<1||lv[v])
             continue;
			lv[v]=lv[u]+1;
			q.push(v);
		}
	}
	return false;
}

int FindFlow(int u,int flow)
{
	if(u==t) return flow;
	else
	{
		int F=0;
		for(int& i=cur[u];~i;i=e[i].next)
		{
			int v=e[i].to;
			if(e[i].val<1||lv[v]!=lv[u]+1)
             continue;
			int w=FindFlow(v,min(e[i].val,flow-F));
			if(!w) lv[v]=-1;
			F+=w;
			e[i].val-=w;
			e[i^1].val+=w;
			if(F>flow) break;
		}
		if(F<flow) lv[u]=-1;
		return F;
	}
}

inline int Dinic(int s,int t)
{
    int ans=0;
    while(level(s,t))
    {
        int x;
        while((x=FindFlow(s,INF)))
         ans+=x;
    }
    return ans;
}

signed main()
{
	//freopen("P1231.in","r",stdin);
	//freopen("P1231.out","w",stdout);
	memset(head,-1,sizeof(head));
    n1=read(),n2=read(),n3=read();
    s=0,t=n1*2+n2+n3+1;
    for(int m=read();m--;)
    {
		int u=read(),v=read();
		DoubleEdge(u+n1,v+n1+n1,1);
	}
	for(int m=read();m--;)
    {
		int u=read(),v=read();
		DoubleEdge(v+n1+n1+n2,u,1);
	}
	for(int i=1;i<=n1;i++) DoubleEdge(i,i+n1,1);
	for(int i=1;i<=n3;i++) DoubleEdge(s,i+n1*2+n2,1);
	for(int i=1;i<=n2;i++) DoubleEdge(i+n1+n1,t,1);
    printf("%d",Dinic(s,t));
	return 0;
}


2024/11/25 07:41
加载中...