Duff in Mafia[CF587D]

发表于 分类于

链接

luogu

题解

最小值最大显然先二分，然后变成有些边一定不能选，有些边可以选。

每条可以选的边有选或者不选两种情况。

对于一个点而言：考虑与之相连的所有边，如果其中一条边选了，剩下的所有的边都不能选；考虑与之相连的所有同颜色的边，如果其中一条边没选，剩下的都必须要选。

那么就变成一个2-SAT问题了。将 $m$ 条边看成点，拆点，$i,i’$ 分别表示表示这条边选和不选的情况。

对于必定不能选的边，连边 $(i,i’)$。

对于第一种情况，即考虑所有边的情况：将这些边排成一列，然后连边 $(i,j’)$，其中 $j\not =i$。

第二种情况同理，连 $(i’,j)$。

但是这样做复杂度高达 $O(m^2\log t)$，无法承受。

考虑优化连边——前缀优化（似乎是2-SAT的一种很经典的连边方式？）。

这里只考虑第一种情况，第二种反过来就好了。

将这些边排成一列，设为 $x_i$ 和 $x_i’$。然后新建两列点 $s_i,s_i’$，用下面的方式连边，即可达到同样的效果。

Edge

于是时间复杂度 $O((n+m)\log t)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=500005;
vector<int> ans,vec[N];
int n,m;
struct edge{
	int x,y,col,t;
}e[N];
vector<int> adj[N];
inline void add(int x,int y)
{
	adj[x].pb(y);
}
int cnt,scc_cnt,bel[N];
int dfn[N],low[N],tim,st[N],top;
bool instack[N];
void dfs(int u)
{
	dfn[u]=low[u]=++tim;
	instack[u]=1; st[++top]=u;
	for(auto v:adj[u])
		if(!dfn[v]) dfs(v),low[u]=min(low[u],low[v]);
		else if(instack[v]) low[u]=min(low[u],dfn[v]);
	if(dfn[u]==low[u])
	{
		instack[u]=0; bel[u]=++scc_cnt;
		for(int v;u!=st[top--];top)
		{
			v=st[top+1]; instack[v]=0; bel[v]=scc_cnt;
		}
	}
}
inline void tarjan()
{
	scc_cnt=top=tim=0;
	fo(i,1,cnt) bel[i]=instack[i]=dfn[i]=low[i]=0;
	fo(i,1,cnt) if(!dfn[i]) dfs(i);
}
inline bool check(int x)
{
	fo(i,1,m) if(e[i].t>x) adj[i].pb(i+m);
	tarjan();
	fo(i,1,m) if(e[i].t>x) adj[i].pop_back();
	fo(i,1,m) if(bel[i]==bel[i+m]) return 0;
	return 1;
}
vector<int> v;
inline void work()
{
	int len=v.size();
	ff(i,0,len)
	{
		cnt+=2;
		add(cnt-1,v[i]); add(v[i]+m,cnt);
		if(i!=len-1) add(v[i+1]+m,cnt-1),add(cnt,v[i+1]),add(cnt+1,cnt-1),add(cnt,cnt+2);
	}
}
int main()
{
	n=read(); m=read();
	fo(i,1,m)
	{
		e[i].x=read(),e[i].y=read(),e[i].col=read(),e[i].t=read();
		vec[e[i].x].pb(i); vec[e[i].y].pb(i);
	}
	cnt=m+m;
	fo(i,1,n)
	if(vec[i].size()>1)
	{
		sort(all(vec[i]),[&](const int &x,const int &y){return e[x].col<e[y].col;});
		int len=vec[i].size();
		ff(j,0,len)
		{
			cnt+=2;
			add(vec[i][j],cnt-1); add(cnt,vec[i][j]+m);
			if(j!=len-1) add(cnt-1,vec[i][j+1]+m),add(vec[i][j+1],cnt),add(cnt-1,cnt+1),add(cnt+2,cnt); 
		}
		for(int j=0,k=0;j<len;j=k)
		{
			for(v.clear();k<len&&e[vec[i][j]].col==e[vec[i][k]].col;k++) v.pb(vec[i][k]);
			work();
		}
	}
	int l=0,r=0,mid;
	fo(i,1,m) r=max(r,e[i].t);
	if(!check(r)) return puts("No")&0;
	for(;l<=r;)
	{
		mid=l+r>>1;
		if(check(mid)) r=mid-1;
		else l=mid+1;
	}
	check(l); ans.clear();
	puts("Yes");
	fo(i,1,m) if(bel[i]<bel[i+m]) ans.pb(i);
	printf("%d %d\n",l,ans.size());
	for(int x:ans) printf("%d ",x);
	return 0;
}