[二分接頭辞最適化建図2-SAT]Codeforces 587 D.Duff in Mafia
二分の答え
1つの点に対して、最大1つの接続されたエッジを削除することができて、それぞれの色は最大1つの接続されたエッジを持つことができて、それでは各点の接続されたエッジを接頭辞で最適化して図を建てることができます
1つの点に対して、最大1つの接続されたエッジを削除することができて、それぞれの色は最大1つの接続されたエッジを持つことができて、それでは各点の接続されたエッジを接頭辞で最適化して図を建てることができます
#include
#include
#include
#include
#include
using namespace std;
const int N=1000010;
int n,m,cnt,tot,G[N];
struct iedge{
int s,t,w,c,g;
}ie[N];
int tmp[N],icnt;
vector e[N];
struct edge{
int t,nx;
}E[N<<1];
inline void addedge(int x,int y,int c,int t,int g){
e[x].push_back({x,y,t,c,g}); e[y].push_back({x,y,t,c,g});
}
vector<int> cc[N];
int tt[N],iit;
inline void addedge(int x,int y){
//cout<
E[++cnt].t=y; E[cnt].nx=G[x]; G[x]=cnt;
}
int vis[N],g[N],dfn[N],low[N],s[N],tp,iiit,ig;
void tarjan(int x){
dfn[x]=low[x]=++iiit; vis[x]=1; s[++tp]=x;
for(int i=G[x];i;i=E[i].nx){
if(!vis[E[i].t]) tarjan(E[i].t);
if(vis[E[i].t]!=2) low[x]=min(low[x],low[E[i].t]);
}
if(dfn[x]==low[x]){
int k; ++ig;
do{ k=s[tp--]; vis[k]=2; g[k]=ig; }while(tp && k!=x);
}
}
int lst[N];
inline bool check(int x){
memset(G,0,sizeof(G)); cnt=0;
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++)
if(ie[i].w>x) addedge(i<<1|1,i<<1);
tot=(m<<1|1)+1;
for(int i=1;i<=n;i++){
++iit;
vector<int> a,b;
for(auto u : e[i]){
if(tt[u.c]!=iit) tt[u.c]=iit,cc[u.c].clear(),a.push_back(u.c);
cc[u.c].push_back(u.g); b.push_back(u.g);
}
if(!b.size()) continue;
addedge(b[0]<<1|1,tot); addedge(tot+1,b[0]<<1);
for(int j=1;j1 <<1),tot+(j<<1));
addedge(tot+(j<<1|1),tot+(j-1<<1|1));
addedge(b[j]<<1|1,tot+(j<<1));
addedge(tot+(j<<1|1),b[j]<<1);
addedge(b[j]<<1|1,tot+(j-1<<1|1));
addedge(tot+(j-1<<1),b[j]<<1);
}
tot+=(b.size()<<1|1)+1;
for(int u : a){
if(cc[u].size()<2) continue;
addedge(cc[u][0]<<1,tot);
addedge(tot+1,cc[u][0]<<1|1);
for(int j=1;j1<<1),tot+(j<<1));
addedge(tot+(j<<1|1),tot+(j-1<<1|1));
addedge(cc[u][j]<<1,tot+(j<<1));
addedge(tot+(j<<1|1),cc[u][j]<<1|1);
addedge(cc[u][j]<<1,tot+(j-1<<1|1));
addedge(tot+(j-1<<1),cc[u][j]<<1|1);
}
tot+=(cc[u].size()<<1|1)+1;
}
}
tp=iiit=ig=0;
for(int i=2;i<=tot;i++)
if(!vis[i]) tarjan(i);
for(int i=1;i<=m;i++)
if(g[i<<1]==g[i<<1|1]) return false;
memcpy(lst,g,sizeof(g));
return true;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x,y,c,t;i<=m;i++)
scanf("%d%d%d%d",&x,&y,&c,&t),ie[i]={x,y,t,c,i},tmp[++icnt]=c;
sort(tmp+1,tmp+1+icnt); icnt=unique(tmp+1,tmp+1+icnt)-tmp-1;
for(int i=1;i<=m;i++) ie[i].c=lower_bound(tmp+1,tmp+1+icnt,ie[i].c)-tmp;
for(int i=1;i<=m;i++) addedge(ie[i].s,ie[i].t,ie[i].c,ie[i].t,i);
int l=0,r=1e9,mid,ans=-1;
//int ss=check(3);
while(l<=r)
check(mid=l+r>>1)?r=(ans=mid)-1:l=mid+1;
vector<int> pt;
if(!~ans) return puts("No"),0;
puts("Yes");
for(int i=1;i<=m;i++)
if(lst[i<<1|1]1]) pt.push_back(i);
printf("%d %d
",ans,pt.size());
for(int u : pt) printf("%d ",u);
return 0;
}