求问
查看原帖
求问
532745
Nangu楼主2023/12/28 22:23
#include <bits/stdc++.h>

#define F(i, j, k) for(int i=(j), ENDD=(k); i<=ENDD; ++i)
#define R(i, j, k) for(int i=(j), ENDD=(k); i>=ENDD; --i)
#define debug(x) cout<<#x<<' '<<x<<'\n'
#define de(x) cout<<#x<<' '<<x<<"  "

using namespace std;

const int N=260, M=7007, INF=2E9;

struct edge{
	int u, v, w, nxt;
}e[M<<1];

int cnt=1, head[N<<1], cur[N<<1], dep[N<<1], s=0, t=N*2-1;

void init(int u, int v, int w){
	e[++cnt]={u, v, w, head[u]}, head[u]=cnt;
	e[++cnt]={v, u, 0, head[v]}, head[v]=cnt;
}

bool bfs(){
	memset(dep, 0, sizeof dep);
	memcpy(cur, head, sizeof head);
	queue<int> q;
	q.push(s), dep[s]=1;
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int i=head[u]; i; i=e[i].nxt){
			int v=e[i].v;
			if(!dep[v] && e[i].w) q.push(v), dep[v]=dep[u]+1;
		}
	}
	return dep[t];
}

int dfs(int now, int s){
	if(now==t) return s;
	int res=0;
	for(int i=cur[now]; i && s; cur[now]=(i=e[i].nxt)){
		int v=e[i].v;
		if(dep[v]==dep[now]+1 && e[i].w){
			int tmp=dfs(v, min(e[i].w, s));
			s-=tmp, e[i].w-=tmp, res+=tmp, e[i^1].w+=tmp;
		}
	}
	return res;
}

int dinic(){
	int res=0;
	while(bfs()) res+=dfs(s, INF);
	return res;
}

int n, m, nxt[N];
bool vis[N];

signed main()
{
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>m;
	F(i, 1, m){
		int u, v;
		cin>>u>>v;
		init(u, v+N, 1);
	}
	F(i, 1, n) init(s, i, 1), init(i+N, t, 1);
	int res=dinic();
//	const int n=::n;
	F(i, 1, cnt>>1)
		if(e[i<<1].w==0) nxt[e[i<<1].u]=e[i<<1].v-N;
	F(i, 1, n) vis[nxt[i]]=1;
	F(i, 1, n)
		if(!vis[i]){
			for(int j=i; j && j<=n; j=nxt[j]){
				cout<<j<<' ';
				if(n==9 && j==10) return 1;
			}
			cout<<'\n';
		}
	cout<<n-res;
 	return 0;
}

这份代码会WA on 12, 然而去掉// const int n=::n;的注释后既可以AC此题,也就是说n的值在后来被改变了。。。这是为啥?

2023/12/28 22:23
加载中...