题意简述
有一个长度为 \(n\) 的数组 \(a\) 和 \(m\) 次操作，\(a_i\) 初始为 \(0\)。每次操作形如 \(l_i,x_i,r_i,y_i\) 表示执行 \(a_{l_i}\leftarrow x_i,a_{r_i}\leftarrow y_i\)，你可以改变 \(m\) 次操作的执行顺序，求最终 \(\sum_{i=1}^n a_i\) 的最大值，并给出执行操作的顺序。
多组数据，\(\sum n,\sum m\le 5\times10^5,1\le x_i,y_i\le 2\)。
分析
由于操作有覆盖性质，正着考虑不方便，所以倒着考虑执行顺序。
我们可以将每种操作分为四个类别：\((+2,+2),(+1,+1),(+1,+2),(+2,+1)\)。
显然把 \((+2,+2)\) 的操作放在最前面执行、将 \((+1,+1)\) 的操作放在最后面执行是最优的，问题在于如何决定 \((+1,+2),(+2,+1)\) 两种操作之间的顺序。为了方便将 \((+2,+1)\) 操作的 \(l_i,r_i\) 交换一下转变为 \((+1,+2)\) 操作来考虑。
考虑有两个 \((+1,+2)\) 操作，设它们分别对 \((x_i,y_i),(z_i,w_i)\) 执行。
如果出现 \(x_i,y_i,z_i,w_i\) 两两不同或者 \(x_i=z_i\) 或者 \(y_i=w_i\) 的情况，那么这两个操作之间顺序是什么都不会影响最终结果。换句话说，这两个操作之间没有什么关系。
但如果出现 \(y_i=z_i\) 或者 \(x_i=w_i\) 的情况，我们就需要讨论一下两个操作的先后顺序了。不妨设 \(y_i=z_i\)，此时若先执行 \((x_i,y_i)\)，\(a_{y_i}\) 会变成 \(2\)，然后执行 \((z_i,w_i)\)，由于 \(a_{y_i}\) 已经被赋值，所以 \(a_{z_i}\leftarrow 1\) 操作无效，此时答案更优。
考虑构建图论模型，将 \(x_i\rightarrow y_i\) 连边，那么以上执行顺序在图中就可以表述为 \(x_i\rightarrow y_i(=z_i)\rightarrow w_i\)，这样，一条路径中除了起点会被赋值为 \(1\)，剩下的点都会被赋值为 \(2\)。
将原图缩点，那么在一个 SCC 中的点，只要随便令其中一个点为起点，就可以让整个 SCC 的所有其他点都被赋值为 \(2\)，而且还可以传到其他的它所连接的 SCC 中。
那我们令哪些点为起点呢？
首先，对于一个有入边的 SCC，只要任意一个直接或间接连接它的 SCC 中有一个起点，那么该 SCC 就能完全被 \(2\) 覆盖。所以我们一定在没有入边的 SCC 中选点。
由于我们最先执行了 \((+2,+2)\) 操作，而若将已经赋好值的点设为起点，该点的值不会被改变，所以我们要尽可能选择已经执行过 \((+2,+2)\) 操作的点。如果没有，那只能任选一个点作为起点了。注意特判不会执行任何操作的点，让它们的值保持为 \(0\)。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#define P__ puts("")
#define pb emplace_back
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
using namespace std;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
inline void write(int x,char ch='\0'){
if(x<0){x=-x;putchar('-');}
int y=0;char z[40];
while(x||!y){z[y++]=x%10+48;x/=10;}
while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
bool Mbg;
const int maxn=5e5+5,maxm=4e5+5,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,m;
struct edge{
int to,nxt,id;
}a[maxn];
int head[maxn],edges;
int u[maxn],v[maxn],tot;
void add_edge(int x,int y,int z){
u[++tot]=x,v[tot]=y;
a[++edges]=(edge){y,head[x],z};
head[x]=edges;
}
int col[maxn];
vector<int>ve[maxn];
vector<int>a22,a11;
int dfn[maxn],low[maxn],sta[maxn],tp,dfncnt;
int scc[maxn],sc;
bool in[maxn];
bool vis[maxn];
void tarjan(int x){
dfn[x]=low[x]=++dfncnt,sta[++tp]=x,vis[x]=1;
graph(i,x,head,a){
int u=a[i].to;
if(!dfn[u])tarjan(u),low[x]=min(low[x],low[u]);
else if(vis[u])low[x]=min(low[x],dfn[u]);
}
if(dfn[x]==low[x]){
++sc;int y;
do{y=sta[tp--];vis[y]=0,scc[y]=sc,ve[sc].pb(y);}while(x^y);
}
}
void dfs(int x,int c){
col[x]=max(col[x],c),vis[x]=1;
graph(i,x,head,a){
int u=a[i].to;a22.pb(a[i].id);
if(!vis[u])dfs(u,2);
}
}
void init(){
edges=dfncnt=tp=tot=sc=0;
rep(i,1,n)head[i]=dfn[i]=low[i]=vis[i]=col[i]=scc[i]=in[i]=0;
rep(i,1,n)ve[i].clear();a22.clear(),a11.clear();
}
void solve_the_problem(){
n=rd(),m=rd();init();
rep(i,1,m){
int x=rd(),y=rd(),z=rd(),w=rd();
col[x]=max(col[x],1),col[z]=max(col[z],1);
if(y==1&&w==1)a11.pb(i);
else if(y==2&&w==2)a22.pb(i),col[x]=2,col[z]=2;
else{if(y>w)swap(x,z);add_edge(x,z,i);}
}
rep(i,1,n)if(!dfn[i])tarjan(i);
rep(i,1,n)vis[i]=0;
rep(i,1,tot)if(scc[u[i]]^scc[v[i]])in[scc[v[i]]]=1;
rep(i,1,n)if(!in[scc[i]]&&col[i]==2&&!vis[i])dfs(i,2);
rep(i,1,n)if(!in[scc[i]]&&col[i]==1&&!vis[i])dfs(i,1);
int ans=0;rep(i,1,n)ans+=col[i];
for(int u:a11)a22.pb(u);
write(ans,10);
reverse(a22.begin(),a22.end());
for(int i:a22)write(i,32);P__;
}
bool Med;
signed main(){
int _=rd();while(_--)solve_the_problem();
}
/*
1
6 10
1 1 2 1
1 1 1 1
5 1 1 2
2 2 5 1
3 1 4 2
3 2 1 2
6 1 2 2
1 1 2 2
3 2 2 1
3 2 4 2
answer:10
貌似能卡掉某篇题解
*/