自动搬运

查看原文

来自洛谷，原作者为

	隔壁泞2的如心 AFO|以某种事物作为代价，以某种代价作为契机……？

搬运于2025-08-24 22:40:32，当前版本为作者最后更新于2022-11-09 00:28:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

令人发指的究极辛巴达多合一题。

给出题人点个赞，数据一点都不水，造出了好多非平凡四元环（

要想做这题，首先你看到这平面图就知道得转对偶，具体在推荐题目第一个矿区的题解里就有。

然后你看到这么一堆位运算就知道要拆位，从高位到低位贪心。

显然，要想拦截成功，从最高位开始：

• 如果外星人在这位有能量，那么我们必须要让外星人花费这点能量，不然之后全堵死也没法拦截。

• 如果外星人在这位没有能量，那么我们可以在这里就把外星人堵死，或者先放它一马，然后外星人不再能通过任何含有此位的边，看看之后会不会有更优的解。

我们的任务变成了如何求出在某位拦截外星人的代价。显然我们加边权时不会进位，这等价于让一些边获得此位，使得所有含有此位（或者之前放过外星人的位）的边构成割。转成对偶图之后，原图的割等价于新图的环。但是以优于 $O(n^2)$ 的复杂度求无向图的最小环，这我不会啊！

再次观察题面，题目隐含了一个极强的条件：图没有重边！没有重边的平面图边数有上限，为 $3n-6$，因此原图中不会没有点的度数不大于 $5$，由于所有边代价一样，我们只要把那个原图中度数最小的点所连的所有边删去，就可以获得每位不大于 $5$ 的代价！

因此，我们可以依次判断新图的最小环是否是 $0/1/2/3/4$，如果都不是就是 $5$。具体地，我们依次判断以下条件。

• 原图是否联通

• 新图是否有自环

• 新图是否有重边

• 原图是否有度数为3的点，如果没有，新图是否有三元环。（套用三元环计数方法）

• 原图是否有度数为4的点，如果没有，新图是否有四元环。（套用四元环计数方法）

然后这题就做完了，我们发现，这看似友好的题面里面隐藏了好多板子……

下面是一些坑点：

• 自环重边不能一起查。

• 联通自环重边必须要在新图上查，特判原图度数行不通。

• 存新图的数组一定要往大了开，新图的点数可能比原图多很多。

下面是代码，不是很可读，也不能拿来对拍，没啥必要看……

#include<cstdio>
#include<vector>
#include<map>
#include<cstring>
#include<cassert>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
struct par{
	int a,b;
	friend bool operator<(par n1,par n2){if(n1.a==n2.a)return n1.b<n2.b;return n1.a<n2.a;}
};
map<par,int> ppc;
vector<int> l1[165432],l2[165432],sol[135],l3[165432];
int n,m,k,px[165432],py[165432],nxt[305416],t[305416],val[305416],tq[305416],bel[305416],dx[305416],dy[305416],t2[305416],dic[305416],mp[165432],xp[165432],cp[165432],ppv[165432];
bool cmp(int a,int b){
	return atan2(dx[a],dy[a])<atan2(dx[b],dy[b]);
}
bool cmp2(int a,int b){
	return t2[a]<t2[b];
}
int ppcdfs(int now,int arg){
	if(ppv[now])return 0;
	ppv[now]=1;
	int crr=0;
	for(int i=0;i<l1[now].size();i++){
		if(!(val[l1[now][i]]&arg))crr+=ppcdfs(t[l1[now][i]],arg);
	}
	return crr+1;
}
void sv(int now,int arg){
	memset(nxt,-1,sizeof(nxt));memset(bel,-1,sizeof(bel));memset(dic,0,sizeof(dic));memset(t2,0,sizeof(t2));memset(t2,0,sizeof(t2));memset(ppv,0,sizeof(ppv));
	int mid=77777777,mida=0;
	for(int i=1;i<=n;i++){
		int cnt=0,mind=0;
		for(int j=0;j<l1[i].size();j++){
			if(!(val[l1[i][j]]&arg))tq[cnt++]=l1[i][j],mind++;
		}
		mid>mind?mid=mind,mida=i:0;
		sort(tq,tq+cnt,cmp);
		for(int i=0;i<cnt-1;i++)nxt[tq[i]]=tq[i+1]^1;nxt[tq[cnt-1]]=tq[0]^1;
	}
	int cnt=0;
	for(int i=0;i<m*2;i++){
		int nw=i;
		if(nxt[nw]==-1||bel[nw]!=-1)continue;
		cnt++;
		while(!~bel[nw]){
			bel[nw]=cnt;
			nw=nxt[nw];
			dic[cnt]++;
		}
	}
	for(int i=1;i<=cnt;i++)l2[i].clear(),l3[i].clear();
	ppc.clear();
	if(ppcdfs(1,arg)!=n)return;
	if(!mid)return;
	if(mid==1){
		for(int j=0;j<l1[mida].size();j++)if(!(val[l1[mida][j]]&arg))sol[now].push_back(l1[mida][j]);
		return;
	}
	for(int i=0;i<m*2;i++){
		if(bel[i]==-1)continue;
		l2[bel[i]].push_back(i);
		t2[i]=bel[i^1];
		if(bel[i]==bel[i^1]){
			sol[now].push_back(i);
			return;
		}
		if(dic[bel[i^1]]>dic[bel[i]]||(dic[bel[i^1]]==dic[bel[i]]&&bel[i^1]>bel[i]))l3[bel[i]].push_back(i);
	}
	if(mid<=2){
		for(int j=0;j<l1[mida].size();j++)if(!(val[l1[mida][j]]&arg))sol[now].push_back(l1[mida][j]);
		return;
	}
	for(int i=0;i<m*2;i++){
		if(bel[i]==-1)continue;
		if(ppc.find({bel[i],bel[i^1]})!=ppc.end()){
			sol[now].push_back(i);
			sol[now].push_back(ppc[{bel[i],bel[i^1]}]);
			return;
		}
		ppc[{bel[i],bel[i^1]}]=i;
	}
	for(int i=1;i<=cnt;i++){
        sort(l2[i].begin(),l2[i].end(),cmp2);
		for(int j=0;j<l2[i].size()-1;j++){
		    assert(t2[l2[i][j]]!=i);
			if(t2[l2[i][j]]==t2[l2[i][j+1]]){
				sol[now].push_back(l2[i][j]);
				sol[now].push_back(l2[i][j+1]);
				return;
			}
		}
	}
	if(mid<=3){
		for(int j=0;j<l1[mida].size();j++)if(!(val[l1[mida][j]]&arg))sol[now].push_back(l1[mida][j]);
		return;
	}
	memset(mp,-1,sizeof(mp));memset(xp,0,sizeof(xp));
	for(int i=1;i<=cnt;i++){
		for(int j=0;j<l3[i].size();j++){
			int ts=t2[l3[i][j]];xp[ts]=i;mp[ts]=l3[i][j];
		}
		for(int j=0;j<l3[i].size();j++){
			int ts=t2[l3[i][j]];
			if(ts==i)continue;
			for(int h=0;h<l3[ts].size();h++){
				if(xp[t2[l3[ts][h]]]==i){
					sol[now].push_back(l3[ts][h]);
					sol[now].push_back(mp[t2[l3[ts][h]]]);
					sol[now].push_back(l3[i][j]);
					return;
				}
			}
		}
	}
	if(mid<=4){
		for(int j=0;j<l1[mida].size();j++)if(!(val[l1[mida][j]]&arg))sol[now].push_back(l1[mida][j]);
		return;
	}
	memset(cp,-1,sizeof(cp));memset(mp,-1,sizeof(mp));memset(xp,0,sizeof(xp));
	for(int i=1;i<=cnt;i++){
		for(int j=0;j<l2[i].size();j++){
			int ts=t2[l2[i][j]];
			for(int h=0;h<l3[ts].size();h++){
				if(t2[l3[ts][h]]==i)continue;
				if(xp[t2[l3[ts][h]]]==i){
					sol[now].push_back(cp[t2[l3[ts][h]]]);
					sol[now].push_back(mp[t2[l3[ts][h]]]);
					sol[now].push_back(l3[ts][h]);
					sol[now].push_back(l2[i][j]);
					return;
				}
				xp[t2[l3[ts][h]]]=i;
				mp[t2[l3[ts][h]]]=l3[ts][h];
				cp[t2[l3[ts][h]]]=l2[i][j];
			}
		}
	}
	if(mid<=5){
		for(int j=0;j<l1[mida].size();j++)if(!(val[l1[mida][j]]&arg))sol[now].push_back(l1[mida][j]);
		return;
	}
	assert(0);
}
signed main(){
	scanf("%*lld%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=n;i++)scanf("%lld%lld",px+i,py+i);
	for(int i=0;i<m;i++){
		int in1,in2,in3;
		scanf("%lld%lld%lld",&in1,&in2,&in3);
		assert(in1!=in2);
		l1[in1].push_back(i*2);l1[in2].push_back(i*2+1);
		t[i*2]=in2;t[i*2+1]=in1;val[i*2]=val[i*2+1]=in3;
		assert(t[i*2]!=t[i*2+1]);
		dx[i*2]=px[in2]-px[in1];dy[i*2]=py[in2]-py[in1];
		dx[i*2+1]=-px[in2]+px[in1];dy[i*2+1]=-py[in2]+py[in1];
	}
	int cur1=0,cur2=0,anss=44444444,fin=66554432;
	for(int i=30;i>=0;i--){
		sv(i,(1<<i)|cur1);
		if(k&(1<<i))cur2+=sol[i].size();
		else{
			(anss>cur2+sol[i].size())?(anss=(cur2+sol[i].size()),fin=i):0;
			cur1|=(1<<i);
		}
	}
	ppc.clear();
	for(int i=30;i>=fin;i--){
		if(i!=fin&&((k&(1<<i))==0))continue;
		for(int j=0;j<sol[i].size();j++){
			par p1={t[sol[i][j]],t[sol[i][j]^1]};if(p1.a>p1.b)swap(p1.a,p1.b);
			if(ppc.find(p1)==ppc.end())ppc[p1]=(1<<i);
			else ppc[p1]=ppc[p1]|(1<<i);
		}
	}
	printf("%u\n",ppc.size());
	for(auto i=ppc.begin();i!=ppc.end();i++){
		printf("%lld %lld %lld\n",(i->first).a,(i->first).b,i->second);
	}
}