D44 2-SAT+前缀优化+二分 CF587D Duff in Mafia

视频链接：

CF587D Duff in Mafia - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N=500005;
int head[N],idx,ne[N*6],to[N*6];
void add(int x,int y){
  to[++idx]=y;ne[idx]=head[x],head[x]=idx;
}
int dfn[N],low[N],stk[N],scc[N],top,tim,cnt;
int n,m;
struct E1{int x,y,col,val;}e1[N]; //读入的边
struct E{int col,x,op;};
vector<E> e[N]; //端点上的边
bool cmp(E x,E y){return x.col<y.col;}

int f(int x,int op){return (x+m*op);}
int p0(int x,int op){return x+m*(op?2:3);}
int p1(int x,int op){return x+m*(op?4:5);}

void tarjan(int x){
  dfn[x]=low[x]=++tim;
  stk[++top]=x;
  for(int i=head[x];i;i=ne[i]){
    int y=to[i];
    if(!dfn[y]){ //若y尚未访问
      tarjan(y);
      low[x]=min(low[x],low[y]);
    }
    else if(!scc[y]) //若y已访问且未处理
      low[x]=min(low[x],dfn[y]);
  }
  if(low[x]==dfn[x]){ //若x是SCC的根
    ++cnt;
    for(int y=-1;y!=x;)
      scc[y=stk[top--]]=cnt;
  }
}
bool check(int mid){
  memset(head,0,sizeof(head));
  memset(dfn,0,sizeof(dfn));
  memset(scc,0,sizeof(scc));
  memset(stk,0,sizeof(stk));
  idx=tim=top=cnt=0;
  
  for(int i=1;i<=n;i++){ //有相同端点的边 选j边则不选其他
    for(int j=0;j<e[i].size();j++){
      add(f(e[i][j].x,0),p0(e[i][j].x,e[i][j].op)); //向下
      add(p1(e[i][j].x,e[i][j].op),f(e[i][j].x,1)); //向下
      if(j!=0){
        add(p0(e[i][j-1].x,e[i][j-1].op),p0(e[i][j].x,e[i][j].op)); //向右
        add(p1(e[i][j].x,e[i][j].op),p1(e[i][j-1].x,e[i][j-1].op)); //向左            
        add(p0(e[i][j-1].x,e[i][j-1].op),f(e[i][j].x,1)); //向右下
        add(f(e[i][j].x,0),p1(e[i][j-1].x,e[i][j-1].op)); //向左下
      }
    }
  }
  for(int i=1;i<=n;i++){ //有相同端点 相同颜色的边 不选这条则选那条
    for(int j=1;j<e[i].size();j++){
      if(e[i][j-1].col==e[i][j].col){
        add(f(e[i][j-1].x,1),f(e[i][j].x,0));
        add(f(e[i][j].x,1),f(e[i][j-1].x,0));
      }
    }
  }
  for(int i=1;i<=m;i++) //边权>mid的边 不选它
    if(e1[i].val>mid) add(f(i,0),f(i,1));
  
  for(int i=1;i<=m*2;i++) if(!dfn[i]) tarjan(i);
  for(int i=1;i<=m;i++) if(scc[i]==scc[i+m]) return 0;
  return 1;
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)
    scanf("%d%d%d%d",&e1[i].x,&e1[i].y,&e1[i].col,&e1[i].val);
  for(int i=1;i<=m;i++){
    e[e1[i].x].push_back({e1[i].col,i,0});
    e[e1[i].y].push_back({e1[i].col,i,1});
  }
  for(int i=1;i<=n;i++){
    sort(e[i].begin(),e[i].end(),cmp); //按颜色值排序
    for(int j=2;j<e[i].size();j++)
      if(e[i][j-2].col==e[i][j].col) //一个点上超过3条同色边
        return puts("No"),0;
  }
  
  int l=-1,r=1e9+1,mid; //二分边权
  while(l+1<r){
    mid=(l+r)>>1;
    check(mid)?r=mid:l=mid;
  }
  if(r==1e9+1) return puts("No"),0;
  if(r==0) return printf("Yes\n0 0"),0;
  check(r); //退出二分时 检测值可能不是r 故再Tarjan一遍
  puts("Yes"); vector<int> e;
  for(int i=1;i<=m;i++)
    if(scc[i]<scc[i+m]) e.push_back(i);
  printf("%d %d\n",r,e.size()); //最小权，匹配边数
  for(int i=0;i<e.size();i++)printf("%d ",e[i]);
}