【Codeforces 587D】Duff in Mafia
2-SAT。
题目大意：
给定一张 $n$ 个点 $m$ 条边的无向图，每条边有颜色 $c_i$ 和时间 $t_i$。
要求选出一个边集 $E$，满足：
- 这个边集是原图的匹配。
- 去掉这个边集后，原图的每种颜色的边都是一个匹配。
- 边集中最大的 $t_i$ 尽可能小。
输出方案或判断无解。
一个边集 $E$ 是原图的匹配，当且仅当不存在一个点，有两条和它相连的边。
题解：
考虑限制条件。
对于第一个限制条件，相当于对一个结点 $v$ 及与它相连的边 $E_v$，选择一条边 $i\in E_v$ 后，就不能选择其他 $E_v$ 中的边了。
对于第二个限制条件，相当于对一个结点 $v$ 和颜色 $c$ 及与它相连的边 $E_{v,c}$，不选一条边 $i\in E_{v,c}$ 后，就必须选择其他 $E_{v,c}$ 中的边了。
每条边有两种状态：选或不选。而每个限制条件为：一条边选/不选，则另一条边选/不选。转化为 2-SAT 问题。
但是这样连边的条数是 $O(m^2)$ 的，我们考虑优化。
以第一个限制条件为例，考虑将 $E_v$ 中的边按一定顺序排列并标号，记布尔变量 $b_{v,i}$ 表示 $E_v$ 中前 $i$ 条边里是否选了一条边。令 $x_i$ 表示是否选择第 $i$ 条边。
那么容易推出以下限制条件：$b_{v,i-1}=1\rightarrow b_{v,i}=1$，$x_{i}=1\rightarrow b_{v,i}=1$，$b_{v,i}=0\rightarrow x_i=0$。其逆否命题同时成立。
相当于我们对原图进行了前缀优化。这个图和直接连边的情况是等价的。
那么我们把边数降到了 $O(m)$。
现在要求 $t_i$ 的最大值最小，我们二分最大值，把超过最大值的边钦定为不选，然后跑 2-SAT 即可。
时间复杂度 $O((n+m)\log t)$。
Code：
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define ID(x,k)((x)*2-(k))
using namespace std;
const int N=1e6+5;
struct edge{
int u,v,c,t;
}E[N];
vector<int>G[N],es[N];
int n,m,nod;
inline bool cmp(int a,int b){return E[a].c<E[b].c;}
inline void addedge(int u,int v){G[u].push_back(v);}
int dfn[N],bel[N],low[N],idx,SCC,sta[N],top;
bool vis[N];
void dfs(int now){
dfn[now]=low[now]=++idx;
vis[now]=1;
sta[++top]=now;
for(int to:G[now])
if(!dfn[to]){
dfs(to);
low[now]=min(low[now],low[to]);
}else if(vis[to])low[now]=min(low[now],dfn[to]);
if(low[now]==dfn[now]){
++SCC;
int v;
do{
v=sta[top--];
vis[v]=0;
bel[v]=SCC;
}while(v!=now);
}
}
bool check(int T){
for(int i=1;i<=m;++i)
if(E[i].t>T)addedge(ID(i,1),ID(i,0));
memset(dfn,0,sizeof dfn);
memset(bel,0,sizeof bel);
idx=SCC=0;
for(int i=1;i<=2*nod;++i)if(!dfn[i])dfs(i);
for(int i=1;i<=m;++i)
if(E[i].t>T)G[ID(i,1)].pop_back();
for(int i=1;i<=nod;++i)
if(bel[ID(i,0)]==bel[ID(i,1)])return 0;
return 1;
}
int main(){
scanf("%d%d",&n,&m);
nod=m;
for(int i=1;i<=m;++i){
scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].c,&E[i].t);
es[E[i].v].push_back(i);
es[E[i].u].push_back(i);
}
for(int i=1;i<=n;++i)if(!es[i].empty()){
sort(es[i].begin(),es[i].end(),cmp);
int lst=es[i][0];
for(int k=1;k<es[i].size();++k){
int d=es[i][k];
++nod;
addedge(ID(lst,1),ID(d,0)),addedge(ID(d,1),ID(lst,0));
addedge(ID(lst,1),ID(nod,1)),addedge(ID(nod,0),ID(lst,0));
addedge(ID(d,1),ID(nod,1)),addedge(ID(nod,0),ID(d,0));
lst=nod;
}
lst=es[i][0];
for(int k=1;k<es[i].size();++k)
if(E[es[i][k]].c!=E[es[i][k-1]].c)lst=es[i][k];else{
int d=es[i][k];
++nod;
addedge(ID(lst,0),ID(d,1)),addedge(ID(d,0),ID(lst,1));
addedge(ID(lst,0),ID(nod,0)),addedge(ID(nod,1),ID(lst,1));
addedge(ID(d,0),ID(nod,0)),addedge(ID(nod,1),ID(d,1));
lst=nod;
}
}
if(!check(1000000000)){
puts("No");
return 0;
}
puts("Yes");
int l=0,r=1e9,ans=1e9;
while(l<=r){
const int mid=l+r>>1;
if(check(mid))r=(ans=mid)-1;else l=mid+1;
}
check(ans);
int tot=0;
for(int i=1;i<=m;++i)
if(bel[ID(i,1)]<bel[ID(i,0)])++tot;
printf("%d %d\n",ans,tot);
for(int i=1;i<=m;++i)
if(bel[ID(i,1)]<bel[ID(i,0)])
printf("%d ",i);
return 0;
}