求助(unkown error)悬关
  • 板块UVA1327 King's Quest
  • 楼主Zikl
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/10/6 00:39
  • 上次更新2023/11/2 15:22:15
查看原帖
求助(unkown error)悬关
300166
Zikl楼主2023/10/6 00:39
//完全匹配的可行边 
//属于匹配边或同一个强连通分量里 
//不完全匹配的可行边
//在网络流残量中tarjan 
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
const int N=2e3+5,M=2e5+N;
using namespace std;
int n,ans[N],ct;
int en,h[N<<1];
struct edge{int n,v;}e[M];
inline void add(const int &x,const int &y){e[++en]=(edge){h[x],y};h[x]=en;}
int stack_[N<<1],dfn[N<<1],low[N<<1],cnt,top,inq[N<<1],cntt;
int inv[N<<1];
void tarjan(int x){
	dfn[x]=low[x]=++cnt;
	stack_[++top]=x;
	inq[x]=1;
	 for(int i=h[x];i;i=e[i].n){
		int y=e[i].v;
		if(!dfn[y]) {
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		if(inq[y])
		low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x]){
		++cntt;
		while(1){
			inq[stack_[top]]=0;
			inv[stack_[top]]=cntt;
			top--;
			if(stack_[top+1]==x) break;
		}
	}
}
inline void write(int x) {
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
inline void clear(){
	cnt=cntt=top=ct=0;
	en=0; 
	memset(h,0,sizeof(h));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(inq,0,sizeof(inq));
	memset(inv,0,sizeof(inv));
}
signed main(){
	while(scanf("%d",&n)!=-1){
	clear();
	for(int i=1;i<=n;i++){
		int k;
	scanf("%d",&k);
		ct=0;
		for(int j=1,x;j<=k;j++){
		scanf("%d",&x);
		add(i,x+n);
		}
	}
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
	add(x+n,i);	
	}
	for(int i=1;i<=n;i++)
	if(!dfn[i]) tarjan(i); 
	for(int u=1;u<=n;u++){
		int num=0;
		 for(int i=h[u];i;i=e[i].n){ 
                int v=e[i].v;
                if(inv[u]==inv[v]) ans[++num]=v-n;
			 }
		sort(ans+1,ans+1+num);
		write(num);
		putchar(' ');
		for(int j=1;j<=num;j++){
			write(ans[j]);
			putchar(' ');
		}
		putchar('\n');
	}}
	return 0;
}

不知道到底出什么问题了,数组开的正常,思路也正常。

2023/10/6 00:39
加载中...