40pts求调
查看原帖
40pts求调
554576
yueluoxingchen楼主2024/7/21 19:51

救救孩子吧,调了几个小时了

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
using namespace std;

const int N=510;
map<int,int> mp;
int m;

struct newnode{
	int size;
	int flag;
	
	newnode(int x,int y):size(x),flag(y){}
	
	newnode operator + (const newnode &t){
		return newnode(size+t.size,(flag + t.flag));
	}
};

struct node{
	int u,v,nxt;
}g[N<<1],rd[N];

int hd[N],cnt;
int testcase,n,t;
int s[N<<1];
int dfn[N],low[N],idx;
bool iscut[N];
long long rescnt,ressum;

void add(int u,int v)
{
	g[++cnt]={u,v,hd[u]};
	hd[u]=cnt;
}

void init()
{
	testcase++;
	n=t=0;
	cnt=1;
	memset(hd,0,sizeof(hd));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(iscut,false,sizeof(iscut));
}

void read()
{
	for(int i=1;i<=m;i++) scanf("%d%d",&rd[i].u,&rd[i].v);
	for(int i=1;i<=m;i++) s[++t]=rd[i].u,s[++t]=rd[i].v;
	sort(s+1,s+t+1);
	for(int i=1;i<=t;i++) 
	{
		if(s[i]!=s[i-1]) mp[s[i]]=++n;
	}
	for(int i=1;i<=m;i++)
	{
		add(mp[rd[i].u],mp[rd[i].v]);
		add(mp[rd[i].v],mp[rd[i].u]);
	}
}

void Tarjan(int now,int father)
{
	dfn[now]=++idx;
	low[now]=idx;
	int child=0;
	for(int i=hd[now];i;i=g[i].nxt)
	{
		int v=g[i].v;
		if(v==father) continue;
		if(!dfn[v])
		{
			child++;
			Tarjan(v,now);
			low[now]=max(low[now],low[v]);
			if(low[v]>=dfn[now]) iscut[now]=true;
		}else if(dfn[v]<low[now]) low[now]=dfn[v];
	}
	if(father==-1 && child==1) iscut[now]=false;
}

newnode op(int now,int father)
{
	if(iscut[now]) return newnode(0,1);
	newnode ans(1,0);
	for(int i=hd[now];i;i=g[i].nxt)
	{
		int v=g[i].v;
		if(v==father) continue;
		if(dfn[v]!=dfn[now]) dfn[v]=dfn[now],ans=ans+op(v,now);
	}
	return ans;
}

int main()
{
	//freopen("P3225_1.in","r",stdin); 
	while(cin>>m)
	{
		if(m==0) break;
		init();
		read();
		for(int i=1;i<=n;i++) 
		{
			if(!dfn[i]) Tarjan(i,-1);
		}
		memset(dfn,0,sizeof(dfn));
		rescnt=0;
		ressum=1;
		for(int i=1;i<=n;i++)
		{
			if(!dfn[i] && !iscut[i])
			{
				dfn[i]=i;
				newnode p=op(i,-1);
				if(p.flag==0) rescnt+=min(p.size,2),ressum*=max(p.size*(p.size-1)/2,1);
				if(p.flag==1) rescnt++,ressum*=p.size;
			}
		}
		printf("Case %d: %lld %lld\n",testcase,rescnt,ressum);
	}
	return 0;
}
2024/7/21 19:51
加载中...