设$D(A)\leq D(B)$，从小到大枚举$D(A)$，双指针从大到小枚举$D(B)$。

那么对于权值不超过$D(A)$的边，可以忽略。

对于权值介于$(D(A),D(B)]$之间的边，需要满足那两个点不能都在集合$A$。

对于权值大于$D(B)$的边，需要满足那两个点不在同一个集合。

所以建图判断2-SAT是否有解即可，这可以使用压位Kosaraju算法。

时间复杂度$O(\frac{n^4}{64})$。

 

#include
     
      #include
      
       #define N 205using namespace std;typedef unsigned long long ll;int n,m,i,j,k,t,q[N<<1],f[N<<1],ans;struct E{int x,y,w;E(){}E(int _x,int _y,int _w){x=_x,y=_y,w=_w;}}e[N*N];inline bool cmp(const E&a,const E&b){return a.w
       
        >6]^=1ULL<<(x&63);}  int get(int x){return v[x>>6]>>(x&63)&1;}}v0,v1,g0[N<<1],g1[N<<1];inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline void addA(int x,int y){  g0[x].flip(y);  g1[y+n].flip(x);  g0[y].flip(x);  g1[x+n].flip(y);}inline void addB(int x,int y){  g0[x+n].flip(y);  g1[y].flip(x);  g0[y+n].flip(x);  g1[x].flip(y);}void dfs1(int x){  if(x
        
         >1;  sort(e+1,e+m+1,cmp);  for(i=0;i
         
          =ans||check()){      ans=min(ans,e[i].w+e[j].w);      if(j)addB(e[j].x,e[j].y);      if((--j)