[ 前后缀优化建图 2-SAT ] Codeforces587D Duff in Mafia

题解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void Read(int& x){
char c=nc();
for(;c<'0'||c>'9';c=nc());
for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());
}
inline void Read(ll& x){
char c=nc();
for(;c<'0'||c>'9';c=nc());
for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());
}
#define N 50010
#define M 2000000
struct Edge{
int x,y,c,f;
}e[N<<1];
vector<int>g[M];
int i,j,k,n,m,p,T,cnt,c[N];
int num,pr[M],sf[M];
int dfn[M],low[M],f[M],st[M],top;
int l,r,t[N];
inline bool Cmp(Edge a,Edge b){
if(a.x==b.x)return a.c<b.c;
return a.x<b.x;
}
inline void Dfs(int x){
dfn[x]=low[x]=++T;st[++top]=x;
for(int i=0;i<g[x].size();i++){
int v=g[x][i];
if(!dfn[v])Dfs(v),low[x]=min(low[x],low[v]);else
if(!f[v])low[x]=min(low[x],dfn[v]);
}
if(low[x]==dfn[x]){
cnt++;
while(st[top]!=x)f[st[top--]]=cnt;
f[st[top--]]=cnt;
}
}
inline bool Check(int x){
for(int i=1;i<=m/2;i++)
if(t[i]>x)g[i*2-1].push_back(i*2);
bool F=1;
memset(dfn,0,sizeof(dfn));
memset(f,0,sizeof(f));
T=cnt=0;
for(int i=1;i<=num;i++)if(!dfn[i])Dfs(i);
for(int i=1;i<=m/2;i++)
if(f[i*2]==f[i*2-1]){
F=0;
break;
}
for(int i=1;i<=m/2;i++)
if(t[i]>x)g[i*2-1].pop_back();
return F;
}
int main(){
Read(n);Read(m);
for(i=1;i<=m;i++)Read(e[i].x),Read(e[i].y),Read(e[i].c),Read(t[i]),e[i].f=i,e[i+m]=e[i],swap(e[i+m].x,e[i+m].y),r=max(r,t[i]);
m<<=1;
sort(e+1,e+m+1,Cmp);
num=m;
for(i=1;i<=m;i=j+1){
pr[i]=++num;sf[i]=++num;
for(j=i;j<=m&&e[j+1].x==e[j].x&&e[j+1].c==e[j].c;)pr[++j]=++num,sf[j]=++num;
for(p=i;p<=j;p++){
if(p>i)g[e[p].f*2].push_back(pr[p-1]),g[pr[p]].push_back(pr[p-1]);
if(p<j)g[e[p].f*2].push_back(sf[p+1]),g[sf[p]].push_back(sf[p+1]);
g[pr[p]].push_back(e[p].f*2-1);g[sf[p]].push_back(e[p].f*2-1);
}
}
for(i=1;i<=m;i=j+1){
pr[i]=++num;sf[i]=++num;
for(j=i;j<=m&&e[j+1].x==e[j].x;)pr[++j]=++num,sf[j]=++num;
for(p=i;p<=j;p++){
if(p>i)g[e[p].f*2-1].push_back(pr[p-1]),g[pr[p]].push_back(pr[p-1]);
if(p<j)g[e[p].f*2-1].push_back(sf[p+1]),g[sf[p]].push_back(sf[p+1]);
g[pr[p]].push_back(e[p].f*2);g[sf[p]].push_back(e[p].f*2);
}
}
if(!Check(r)){
puts("No");
return 0;
}
while(l<=r){
int Mid=l+r>>1;
if(Check(Mid))r=Mid-1;else l=Mid+1;
}
puts("Yes");
Check(l);
k=0;
for(i=1;i<=m/2;i++)
if(f[i*2-1]<f[i*2])c[++k]=i;
printf("%d %dn",l,k);
for(i=1;i<=k;i++)printf("%d ",c[i]);
return 0;
}

最后

以上就是醉熏故事为你收集整理的[ 前后缀优化建图 2-SAT ] Codeforces587D Duff in Mafia的全部内容，希望文章能够帮你解决[ 前后缀优化建图 2-SAT ] Codeforces587D Duff in Mafia所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。