P8596 一个拦的截 题解
令人发指的究极辛巴达多合一题。
给出题人点个赞，数据一点都不水，造出了好多非平凡四元环（
要想做这题，首先你看到这平面图就知道得转对偶，具体在推荐题目第一个矿区的题解里就有。
然后你看到这么一堆位运算就知道要拆位，从高位到低位贪心。
显然，要想拦截成功，从最高位开始：
-
如果外星人在这位有能量，那么我们必须要让外星人花费这点能量，不然之后全堵死也没法拦截。
-
如果外星人在这位没有能量，那么我们可以在这里就把外星人堵死，或者先放它一马，然后外星人不再能通过任何含有此位的边，看看之后会不会有更优的解。
我们的任务变成了如何求出在某位拦截外星人的代价。显然我们加边权时不会进位，这等价于让一些边获得此位，使得所有含有此位（或者之前放过外星人的位）的边构成割。转成对偶图之后，原图的割等价于新图的环。但是以优于
再次观察题面，题目隐含了一个极强的条件：图没有重边！没有重边的平面图边数有上限，为
因此，我们可以依次判断新图的最小环是否是
-
原图是否联通
-
新图是否有自环
-
新图是否有重边
-
原图是否有度数为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);
}
}