(POJ - 2912) rochambau (weighted concurrent search + enumeration)

Topic link ：2912 -- Rochambeau

The question ：n There is a play for a little partner to guess fists , Except for a clever guy , Others will only produce a single kind , give m The result of guessing boxing , Ask to find out the serial number of the clever little partner , And the output in the first few guesses can be determined .（ Be careful <,>,= There may be spaces before and after ）

analysis ： Everyone can only have three choices , So this problem is more similar to that of the food chain , If you don't know about weighted search set, you can look at that question first , Attach the blog address here ：POJ - 1182 The food chain （ Take the right and check the collection ）_AC__dream The blog of -CSDN Blog a​​​​​​

First of all, it is certain that except for the smart little partner who may have conflicts with others , There will be no contradiction between others （ Because others can only make a single gesture , This information is crucial ）, So we can enumerate smart friends , Remove the result of guessing about a little partner every time , If there are still contradictions, the little partner can't be the smart one , On the contrary, the partner may be a smart partner , After enumerating all the partners in this way , If the number of smart partners is 0, It shows that removing any small partner cannot eliminate the contradiction , Then there are at least two smart friends （ Pay attention to distinguish this sentence from “ One of these two may be a smart partner ”）. If the number of smart partners may be greater than 1, It means that smart partners are random , Whoever it is . In addition to the above two cases , The rest is that smart friends are the only , Then how should we determine which sentence is judged ？

Because I said before , The result of a contradictory fist guessing must include smart partners , It may be assumed that the order of contradiction with smart partners is a1,a2,……, So when we judge that a smart partner and a2 When there is a contradiction between them, the number of sentences can be judged , In the initial enumeration process, remove a2, Then the contradiction must be with a1（ Because the enumeration process is to remove a small partner , When there are contradictions, it can be judged that what is currently removed is not a smart little partner , Directly break）, Otherwise, the contradiction must be with a2, So we only need to record the maximum value of each contradictory statement , In this way, we can get the position of the statement

Here is the code ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=3e3+10;
int fu[N],d[N],n,m;
int a[N],b[N];
char op[N];
void init()
{
	for(int i=1;i<=n;i++)
		fu[i]=i,d[i]=0;
}
int find(int x)
{
	int t=fu[x];
	if(x!=fu[x]) fu[x]=find(fu[x]);
	d[x]=(d[t]+d[x])%3;
	return fu[x];
}
void merge(int x,int y,int z)
{
	int f1=find(x),f2=find(y);
	fu[f2]=f1;
	d[f2]=(d[x]+z-d[y]+6)%3;
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=1;i<=m;i++)
		{
			scanf("%d%c%d",&a[i],&op[i],&b[i]);
			a[i]++;b[i]++;// Label from 1 Start  
		}
		int ans=0;// Record the possible number of referees 
		int pos;// Record possible referees 
		int p=0;// Record where contradictions are found 
		for(int i=1;i<=n;i++)
		{
			init();
			bool flag=true;// When the contradiction turns into false 
			for(int j=1;j<=m;j++)
			{
				if(a[j]==i||b[j]==i) continue;
				if(op[j]=='<')
				{
					int f1=find(a[j]),f2=find(b[j]);
					if(f1!=f2)
						merge(a[j],b[j],1);
					else if((d[a[j]]+1)%3==d[b[j]]) continue;
					else// Find contradictions  
					{
						p=max(p,j);
						flag=false;
						break; 
					}
				}
				else if(op[j]=='>')
				{
					int f1=find(a[j]),f2=find(b[j]);
					if(f1!=f2)
						merge(a[j],b[j],-1);
					else if(d[a[j]]==(d[b[j]]+1)%3) continue;
					else// Find contradictions  
					{
						p=max(p,j);
						flag=false;
						break; 
					}
				}
				else
				{
					int f1=find(a[j]),f2=find(b[j]);
					if(f1!=f2)
						merge(a[j],b[j],0);
					else if(d[a[j]]==d[b[j]]) continue;
					else// Find contradictions  
					{
						p=max(p,j);
						flag=false;
						break; 
					}
				}
			}
			if(flag) pos=i,ans++;
			if(ans>1) break;
		}
		if(ans>1) puts("Can not determine");
		else if(!ans) puts("Impossible");
		else printf("Player %d can be determined to be the judge after %d lines\n",pos-1,p);
	}
	return 0;
}