P7056 Insider’s Information

题目大意

给定 $m$ 个三元组，你需要给出一个序列满足其中的任意至少 $\lceil \frac{m}{2} \rceil$ 个三元组。

思路

定义每个三元组为 $[a_i,b_i,c_i]$，则满足的条件是 $b_i$ 处于 $a_i$ 与 $c_i$ 之间。
不难发现若仅计算这一个三元组对答案产生的贡献，则 $a_i$ 与 $c_i$ 是等价的，交换它们的位置不会影响贡献。
不难想到对所有点进行拓扑排序，确定 $b_i$ 一定在 $a_i$ 与 $c_i$ 后被填入。
所以分别连 $a_i$ 到 $b_i$ 的边及 $c_i$ 到 $b_i$ 的边，每个三元组中的 $b_i$ 入度每次加二。
然后进行拓扑排序，但在减去删去点的关联点入度时判断是否已经被减过（先遍历到了另外一端的端点），若未被减过，则将其入度减二，否则不减。
在拓扑排序后考虑按拓扑序填入答案，记 $ord_i$ 为拓扑序的第 $i$ 个数，计算其放在前端和后端分别能产生多少贡献，从两边往中间填充。

Code

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
#include<bits/stdc++.h>
#define fir first
#define sec second 
#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
	template<typename T>inline void read(T &x){
		x=0;int f=1;char c=getchar();
		for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
		for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
	}
	template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);
        read(args...);
    }
	template<typename T>void print(T x){
		if(x<0)x=-x,putchar('-');
		if(x>9)print(x/10);
		putchar(x%10+48);
	}
}
using namespace std;
using namespace FastIO;
const int N=1e5+7;
int n,m,rud[N],a[N],b[N],c[N],vis[N],typ[N];
vector<int>G[N],ord;
deque<int>fr,bk;
queue<int>q;
signed main(){
	read(n,m);
	rep(i,1,m){
		read(a[i],b[i],c[i]);
		G[a[i]].emplace_back(i);
		G[c[i]].emplace_back(i);
		rud[b[i]]+=2;
	}
	rep(i,1,n){
		if(rud[i]==0){
			q.push(i);
		}
	}
	while(q.size()){
		int u=q.front();
		ord.emplace_back(u);
		q.pop();
		fep(i,0,G[u].size()){
			int id=G[u][i];
			if(vis[id])continue;
			vis[id]=1;
			int v=b[id];
			rud[v]-=2;
			if(rud[v]==0){
				q.push(v);
			}
		}
	}
	fep(i,0,ord.size()){
		int now=ord[i],vfr=0,vbk=0;
		fep(j,0,G[now].size()){
			int id=G[now][j];
			int ot=a[id]+c[id]-now;//另外一个端点 
			int mdl=b[id];
			if(typ[mdl]!=0)continue;
			if(typ[ot]==1){
				vbk++;
			}
			if(typ[ot]==3){
				vfr++;
			}
		}
		if(vbk>=vfr){
			typ[now]=3;
			bk.push_front(now);
		}
		else{
			typ[now]=1;
			fr.push_back(now);
		}
	}
	while(fr.size()){
		int x=fr.front();
		fr.pop_front();
		print(x);
		putchar(' ');
	}
	while(bk.size()){
		int x=bk.front();
		bk.pop_front();
		print(x);
		putchar(' ');
	}
}