求助大佬,#51T了
  • 板块CF891C Envy
  • 楼主我爱杨帆
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/11/26 15:09
  • 上次更新2023/11/5 07:18:48
查看原帖
求助大佬,#51T了
363495
我爱杨帆楼主2020/11/26 15:09
#include<bits/stdc++.h>
#define int long long 
#define re register
#define inf 1e18
//#define double l double
const int mod=998244853,pow10=1024;
const int sz2=3005;
const int sz=2e6+5;
using namespace std;
int read()
{
	char c=getchar();
	int r=0,f=1;
	while((c<'0'||c>'9')&&c!='-')
		c=getchar();
	if(c=='-') {
		f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		r=r*10+c-'0';
		c=getchar();
	}
	return f*r;
}
struct node
{
	int u,v,w;
}e[sz];
struct node1
{
	int fx,fy;
}stk[sz];
struct node2
{
	int num,id;
};
int n,m,fa[sz],siz[sz],top,tmp[sz],val[sz],Ans[sz],U[sz],V[sz],sum;
vector <int >ask[sz];
int getfa(int x)
{   
	if(x!=fa[x]) return getfa(fa[x]);
	else return x;
}
bool merge(int x,int y)
{
	int fx=getfa(x),fy=getfa(y);
    if(fx==fy) return 0;
    if(siz[fx]<siz[fy]) swap(fx,fy);
    siz[fx]+=siz[fy],fa[fy]=fx;
    stk[++top]=((node1){fx,fy});
	return 1;
}
void dele()
{
    while(top)
	{
	  fa[stk[top].fy]=stk[top].fy,siz[stk[top].fx]-=siz[stk[top].fy];
	  top--;	
	}	
}
bool cmp(node x,node y)
{
	return x.w<y.w;
}
bool cmp1(int x,int y)
{
	return val[x]<val[y];//!!!!
}
bool cmp2(vector<int > x,vector<int  > y)
{							
	return val[x[1]]<val[y[1]];
}									
signed main()
{
//	memset(Ans,-1,sizeof(Ans));
    n=read(),m=read();
    for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
	for(int i=1;i<=m;i++)
    {
    	int u=read(),v=read(),w=read();
    	e[i]=((node){u,v,w});
		val[i]=w,U[i]=u,V[i]=v;
	}
	sort(e+1,e+1+m,cmp);
    int q=read();
    for(int i=1;i<=q;i++)
    {		
        Ans[i]=1;
    	int k=read();
    	for(int j=1;j<=k;j++)  tmp[j]=read();
    	sort(tmp+1,tmp+1+k,cmp1);
	    for(int j=1;j<=k;j++) 
		{
			if(val[tmp[j]]!=val[tmp[j-1]]) ask[++sum].push_back(i);    		
			ask[sum].push_back(tmp[j]);
	    }
	}		
	sort(ask+1,ask+1+sum,cmp2);
    int res=1,now=0;
	for(int i=1;i<=sum;i++)
    {   
       int fla=0;
       for(int j=res;j<=m;j++)
       {	  
       	  if(now==n-1) { 
       	  	fla=1;
       	  	break;
			 } 
	      if(e[j].w<val[ask[i][1]]) 
          {      
          	int fx=getfa(e[j].u),fy=getfa(e[j].v);
			if(fx==fy) continue;
			if(siz[fx]<siz[fy]) fa[fx]=fy,siz[fy]+=siz[fx];
			else                fa[fy]=fx,siz[fx]+=siz[fy]; 
		    now++;
		  }      
		  else {     
		  	res=j; 
			break; 
	      }         
	   }        
	   if(fla) {    
	   	Ans[ask[i][0]]&=0;
	   	continue;
	   }   
	   for(int j=1;j<ask[i].size();j++)
	      if(!merge(U[ask[i][j]],V[ask[i][j]])) {  
	         fla=1;break;	
		  }   
	   if(fla) 
	   	Ans[ask[i][0]]&=0;
	   dele(); 
	}
	for(int i=1;i<=q;i++) 
	{    
	    if(Ans[i]) puts("YES"); 
        else       puts("NO");
	}
} 
/*
8 17
1 5 4
1 4 2
2 4 3
1 2 2
2 3 4
3 4 2
3 7 3
4 7 2
4 6 2
5 6 3
6 7 4
6 9 2
6 8 3
7 9 2
8 9 2
7 8 3
4 5 3
10
4 5 3 2 4
2 3 6
5 3 2 1 5 14
6 2 13 12 10 15 5
7 12 11 13 15 2 3 4
4 3 2 16 17
3 12 12 11
3 12 13 11
4 12 11 5 7
5 2 13 14 12 11
*/
2020/11/26 15:09
加载中...