P3225 tarjan 悬关求调
  • 板块灌水区
  • 楼主Brainless_zxc
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/1/26 10:50
  • 上次更新2024/1/26 14:04:57
查看原帖
P3225 tarjan 悬关求调
661274
Brainless_zxc楼主2024/1/26 10:50

rt,这份代码样例都过不去但是查不出什么错

#include<bits/stdc++.h>
using namespace std;
const int MAXN=501;
long long int ans=0,fanganshu=1;
int n,m,u,v,fenliangtot=0,casenum=0;
int zhan[MAXN],top=0;
int visit=0,dfn[MAXN],low[MAXN];
int root[MAXN],num[MAXN],roottot=0;
bool vis[MAXN];
struct fenliang{
	int num,gediannum;
	fenliang(){
		num=0;
		gediannum=0;
	}
}group[MAXN];
struct edge{
	int v;
	edge *NEXT;
	edge(){
		v=0;
		NEXT=NULL;
	}
}*con[MAXN];
void ins(int start,int end){
	edge *p=new(edge);
	p->v=end;
	p->NEXT=con[start];
	con[start]=p;
}
void tarjan(int nv){
	dfn[nv]=low[nv]=++visit;
	for(edge *p=con[nv];p;p=p->NEXT){
		int vv=p->v;
		if(dfn[vv]==0){
			tarjan(vv);
			low[nv]=min(low[nv],low[vv]); 
			if(low[vv]>=dfn[nv]){
				
			}++num[nv];
		}
		else{
			low[nv]=min(low[nv],dfn[vv]);
		}
	}
}
void dfs(int nv){
	vis[nv]=true;
	zhan[++top]=nv;
	for(edge *p=con[nv];p;p=p->NEXT){
		int vv=p->v;
		if(vis[vv]==false){
			dfs(vv);
			if(low[vv]>=dfn[nv]){
				++fenliangtot;
				int place=zhan[top];
				while(place!=nv){
					--top;
					if(num[place]){
						++group[fenliangtot].gediannum; 
					}
					else{
						++group[fenliangtot].num;
					}
					place=zhan[top];
				}
				if(num[place]){
					++group[fenliangtot].gediannum;
				}
				else{
					++group[fenliangtot].num;
				}
			}
		}
	}
}
int main(){
	while(1){
		cin>>m;
		if(m==0) return 0;
		memset(con,0,sizeof(con));
		memset(dfn,0,sizeof(dfn));
		memset(num,0,sizeof(num));
		memset(vis,0,sizeof(vis));
		memset(group,0,sizeof(group));
		ans=n=roottot=fenliangtot=0;
		fanganshu=1;
		while(m--){
			cin>>u>>v;
			n=max(n,max(u,v));
			ins(u,v);
			ins(v,u);
		}
		for(int i=1;i<=n;i++){
			if(dfn[i]==0){
				root[++roottot]=i;
				tarjan(i);
			}
		}
		for(int i=1;i<=roottot;i++){
			if(num[root[i]]!=0){
				--num[root[i]];
			}
		}
		for(int i=1;i<=n;i++){
			if(vis[i]==false){
				dfs(i);
			}
		}
		for(int i=1;i<=fenliangtot;++i){
			int a=group[i].num,b=group[i].gediannum;
			if(b>=2){
				continue;
			}
			else if(b==1){
				++ans;
				fanganshu*=a;
			}
			else if(b==0){
				ans+=2;
				fanganshu*=(a*(a-1)/2);
			}
		}
		cout<<"Case "<<++casenum<<": "<<ans<<" "<<fanganshu<<endl;
	}
}
2024/1/26 10:50
加载中...