[cf587D]Duff in Mafia

二分最大边权，即有些边强制不能被选

接下来，即任意一点上某两边不能同时被选，以及任意一点上颜色相同的两边必须被选择一条

这些限制都可以用2-sat的形式来描述（强制不能选即连边"选->不选"），但后两类的边数达到了$o(m^{2})$，时间复杂度上无法接受

当一个节点上有一种颜色的边出现3次，或有两种颜色的边出现两次，必然不合法，因此第3类限制的边每一个点上至多只有1条，即为$o(n)$

对于第2类限制，即该点上任意一边都要向其余边连线，那么即新建一些点来优化连边

更具体的，假设某个点上相关的边分别对应点$a_{1},a_{2},...,a_{k}$和$a'_{1},a'_{2},...,a_{k}$（后者表示不选），即需要连边$(a_{i},a'_{j})$（其中$i\ne j$）

新建$s_{1},s_{2},...,s_{k}$，连边$(s_{i},s_{i-1})$和$(s_{i},a'_{i})$，再连边$(a_{i},s_{i-1})$即实现了连边$(a_{i},a'_{j})$（其中$j<i$）

对于$j>i$类似，即连边$(s'_{i},s'_{i+1})$和$(s'_{i},a'_{i})$，再连边$(a_{i},s'_{i+1})$即可

综上，即将边数优化为$o(m)$，可以通过

（关于这个，也可以理解为前后缀的构造）

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 100005

  4 struct Edge{

  5     int nex,to,color,len;

  6 }edge[N];

  7 vector<int>v,ans,A[N*3],B[N*3];

  8 map<int,int>tot,lst;

  9 int V,E,n,m,x,y,c,z,scc,head[N],vis[N*3],dfn[N*3],bl[N*3];

 10 void add_edge(int x,int y,int c,int z){

 11     edge[E].nex=head[x];

 12     edge[E].to=y;

 13     edge[E].color=c;

 14     edge[E].len=z;

 15     head[x]=E++;

 16 }

 17 void add_2sat(int x,int y){

 18     A[x].push_back(y);

 19     B[y].push_back(x);

 20 }

 21 void del_2sat(int x,int y){

 22     A[x].pop_back();

 23     B[y].pop_back();

 24 }

 25 void dfs1(int k){

 26     if (vis[k])return;

 27     vis[k]=1;

 28     for(int i=0;i<A[k].size();i++)dfs1(A[k][i]);

 29     dfn[++dfn[0]]=k;

 30 }

 31 void dfs2(int k){

 32     if (bl[k])return;

 33     bl[k]=scc;

 34     for(int i=0;i<B[k].size();i++)dfs2(B[k][i]);

 35 }

 36 bool calc(int k){

 37     for(int i=0;i<E;i+=2)

 38         if (edge[i].len>k)add_2sat((i>>1),(i>>1)+m);

 39     scc=dfn[0]=0;

 40     memset(vis,0,sizeof(vis));

 41     memset(bl,0,sizeof(bl));

 42     for(int i=0;i<V;i++)

 43         if (!vis[i])dfs1(i);

 44     for(int i=dfn[0];i;i--)

 45         if (!bl[dfn[i]]){

 46             scc++;

 47             dfs2(dfn[i]);

 48         }

 49     bool flag=1;

 50     for(int i=0;i<m;i++)

 51         if (bl[i]==bl[i+m]){

 52             flag=0;

 53             break;

 54         }

 55     for(int i=0;i<E;i+=2)

 56         if (edge[i].len>k)del_2sat((i>>1),(i>>1)+m);

 57     return flag;

 58 }

 59 int main(){

 60     scanf("%d%d",&n,&m);

 61     memset(head,-1,sizeof(head));

 62     for(int i=1;i<=m;i++){

 63         scanf("%d%d%d%d",&x,&y,&c,&z);

 64         add_edge(x,y,c,z);

 65         add_edge(y,x,c,z);

 66     }

 67     V=(m<<1);

 68     for(int i=1;i<=n;i++){

 69         x=y=-1;

 70         v.clear(),tot.clear(),lst.clear();

 71         for(int j=head[i];j!=-1;j=edge[j].nex){

 72             tot[edge[j].color]++;

 73             if (tot[edge[j].color]>2){

 74                 printf("No");

 75                 return 0;

 76             }

 77             if (tot[edge[j].color]==2){

 78                 if ((x>=0)&&(y>=0)){

 79                     printf("No");

 80                     return 0;

 81                 }

 82                 x=(lst[edge[j].color]>>1);

 83                 y=(j>>1);

 84             }

 85             lst[edge[j].color]=j;

 86             v.push_back(j>>1);

 87         }

 88         if ((x>=0)&&(y>=0)){

 89             add_2sat(x+m,y);

 90             add_2sat(y+m,x);

 91         }

 92         for(int j=0;j<v.size();j++){

 93             add_2sat(V+j,v[j]+m);

 94             add_2sat(V+j+v.size(),v[j]+m);

 95         }

 96         for(int j=1;j<v.size();j++){

 97             add_2sat(V+j,V+j-1);

 98             add_2sat(V+j+v.size()-1,V+j+v.size());

 99             add_2sat(v[j],V+j-1);

100             add_2sat(v[j-1],V+j+v.size());

101         }

102         V+=(v.size()<<1);

103     }

104     int l=0,r=0x3f3f3f3f;

105     while (l<r){

106         int mid=(l+r>>1);

107         if (calc(mid))r=mid;

108         else l=mid+1;

109     }

110     if (l==0x3f3f3f3f)printf("No");

111     else{

112         calc(l);

113         for(int i=0;i<m;i++)

114             if (bl[i]>bl[i+m])ans.push_back(i+1);

115         printf("Yes\n%d %d\n",l,ans.size());

116         for(int i=0;i<ans.size();i++)printf("%d ",ans[i]);

117     }

118 }

巴特西

[cf587D]Duff in Mafia

最新文章

热门文章