求助!第7个点TLE
查看原帖
求助!第7个点TLE
388889
daishuchen2010楼主2024/7/24 20:32
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5,inf = 0x3f3f3f3f;
struct edge
{
	int nxt,to,val,F;
}e[MAXN * 4];
int head[MAXN],HEAD[MAXN],tot,a[MAXN],d[MAXN],start,finish,b[MAXN],ts,P[MAXN],Q[MAXN],idp[MAXN],idq[MAXN],que[10000005];
bool in[MAXN],vis[MAXN];
inline void merge(int u,int v,int f)
{
	e[++tot] = {head[u],v,1,f},head[u] = tot;
	e[++tot] = {head[v],u,1,0},head[v] = tot;
}
inline bool SPFA()
{
	int u,v,w,f,l = 1,r = 0;
	for (int i = 1; i <= ts; i++) d[i] = inf,HEAD[i] = head[i];
	que[++r] = start,in[start] = true,d[start] = 0;
	while (l <= r)
	{
		u = que[l++],in[u] = false;
		for (int i = head[u]; i; i = e[i].nxt)
		{
			v = e[i].to,w = e[i].val,f = e[i].F;
			if (!f) continue;
			if (d[v] == inf)
			{
				d[v] = d[u] + w;
				if (!in[v]) que[++r] = v,in[v] = true;
			}
		}
	}
	return (d[finish] != inf);
}
inline int dfs(int u,int rest)
{
	if (u == finish) return rest;
	vis[u] = true;
	int v,w,f,used = 0,tmpF;
	for (int i = HEAD[u]; i; i = e[i].nxt)
	{
		HEAD[u] = i;
		v = e[i].to,w = e[i].val,f = e[i].F;
		if (!f || d[v] != d[u] + w || vis[v]) continue;
		tmpF = dfs(v,min(rest,f));
		if (!tmpF) continue;
		rest -= tmpF,used += tmpF,e[i].F -= tmpF;
		e[(i & 1) ? (i + 1) : (i - 1)].F += tmpF;
	}
	vis[u] = false;
	return used;
}
inline int dinic()
{
	int ans = 0;
	while (SPFA()) ans += dfs(start,inf);
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,x,ans;
	cin >> n,ans = n;
	for (int i = 1; i <= n; i++) cin >> a[i],a[i]++;
	for (int i = 1; i <= n; i++) cin >> b[i],b[i]++;
	start = ++ts,finish = ++ts;
	for (int i = 1; i <= n; i++)
	{
		if (!P[i])
		{
			x = i;
			do
			{
				P[x] = i;
//				cout << x << '\n';
				x = a[x];
			}
			while (x != i);
			if (a[i] != i) idp[i] = ++ts;
		}
		if (!Q[i])
		{
			x = i;
			do
			{
				Q[x] = i;
//				cout << x << '\n';
				x = b[x];
			}
			while (x != i);
			if (b[i] != i) idq[i] = ++ts;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (a[i] == i && b[i] == i) ans--;
		else if (a[i] != i && b[i] != i)
		{
			if (a[i] == b[i]) merge(idp[P[i]],idq[Q[i]],1),merge(idq[Q[i]],idp[P[i]],1);
			else merge(idp[P[i]],idq[Q[i]],1);
		}
		else//a[i]==i or b[i]==i
		{
			if (a[i] == i) merge(start,idq[Q[i]],1);
			else merge(idp[P[i]],finish,1);
		}
	}
	cout << ans - dinic() << '\n';
	return 0;
}
2024/7/24 20:32
加载中...