Starters 191-Coloured Array（无向图边的定方向问题）

思路讲解

一般来说，这种绿题图论建模都是有套路的，一般来说就是在一个联通图内匹配符合一些性质（可能匹配数量直接和V和E相关，也有可能跑一个dfs就出来了）。

我仔细看了一下，感觉可以转化为无向图边的重定向问题 CF-1021-D. Baggage Claim 。

这些是整段代码最重要的部分。其实这部分成立的原因是该子图是联通的（虽然是废话）。

那么我们可以想到一种构造方式，就是从*点（完美匹配点，若没有就从双边点向外延伸，若还没有就无所谓了）出发，然后定向，形成像树一样的形状。

ll size=fa.size(i);
ll edge=fa.edge[fa.find(i)];
ll mcc=fa.mcc[fa.find(i)];
// 现在这里的ans意思是我可以白嫖多少元素
ans+=2*mcc+min(edge,size-mcc);

AC代码

https://www.codechef.com/viewsolution/1167249816

源代码

// Problem: Coloured Array
// Contest: CodeChef - START191D
// URL: https://www.codechef.com/START191D/problems/COLARR7
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORS(i, a, b, step) for (int i=(a);i<=(b);i+=(step))
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
bool mc2[MAXN],exis[MAXN];
/*

*/
inline void init(){
	FOR(i,1,N*2+5){
		A[i]=0;
	}
	FOR(i,1,N*2+5){
		mc2[i]=0;
		exis[i]=0;
	}
}
struct DSU { // 并查集
    vector < int > fa, siz, mcc, edge;
    int ln;
    DSU(int n) {
        ln = n;
        fa.resize(ln + 5, 0), siz.resize(ln + 5, 0), mcc.resize(ln+5, 0);
        edge.resize(ln+5,0);
        FOR(i, 1, n) {
            fa[i] = i;
            if(exis[i]) siz[i] = 1;
            if(mc2[i]) mcc[i]=1;
        }
    }
    int find(int x) {
        while (fa[x] != x) {
            x = fa[x];
            fa[x] = fa[fa[x]];
        }
        return x;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
        	edge[x]+=1;
            return false;
        }
        siz[x] += siz[y];
        fa[y] = x;
        mcc[x]+=mcc[y];
        edge[x]+=edge[y]+1;
        return true;
    }
    int size(int x) {
        return siz[find(x)];
    }
    int countFa() {
        int res = 0;
        FOR(i, 1, ln) {
            if (fa[i] == i) ++res;
        }
        return res;
    }
};
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,2*N){
		cin>>A[i];
	}
	N=2*N;
	for(int i=1;i<=N;i+=2){
		if(A[i]==A[i+1]){
			mc2[A[i]]=true;
		}
		exis[A[i]]=true,exis[A[i+1]]=true;
	}
	DSU fa(N);
	for(int i=1;i<=N;i+=2){
		fa.merge(A[i],A[i+1]);
	}
	vector<bool> vis(N+5,0);
	ll ans=0,al=0;
	FOR(i,1,N){
		if(vis[fa.find(i)]){
			continue;
		}
		vis[fa.find(i)]=true;
		ll size=fa.size(i);
		ll edge=fa.edge[fa.find(i)];
		ll mcc=fa.mcc[fa.find(i)];
		// 现在这里的ans意思是我可以白嫖多少元素
		ans+=2*mcc+min(edge,size-mcc);
#ifdef LOCAL
	debug(ans);
    debug(size);
    debug(edge);
    debug(mcc);
    debug(al);
    debug(max(0ll,min(edge,size-mcc)));
#endif
	}
	ans=N-ans;
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
1
3
1 1 1 3 1 3

3
*/

心路历程（WA，TLE，MLE……）

WA https://www.codechef.com/viewsolution/1167153030

就是贪心做法，优先处理比较独特的。

显然会被相等的一些hack数据hack

1
3
1 3 2 3 1 2

3

源代码

// Problem: Coloured Array
// Contest: CodeChef - START191D
// URL: https://www.codechef.com/START191D/problems/COLARR7
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
inline void init(){
	FOR(i,1,N*2+5){
		A[i]=0;
	}
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,2*N){
		cin>>A[i];
	}
	N=2*N;
	vector<set<ll> > g(N);
	vector<ll> valid(N,0);
	ll ans=0;ll al=0;
	for(int i=1;i<=N;i+=2){
		if(A[i]==A[i+1]){
			if(valid[A[i]]==0){
				valid[A[i]]=1;
			}else{
				ans+=2;
			}
			al+=2;
		}else{
			g[A[i]].insert(i);g[A[i+1]].insert(i+1);
		}
	}
// #ifdef LOCAL
    // cerr <<"OK1";
// #endif
	sort(all(g),[](const set<ll> &a,const set<ll> &b){return SZ(a)<SZ(b);} );
	vector<ll> ma(N+5,0);
	FOR(i,1,N-1){	// A[]->idx
		if(g[i].empty()) continue;
		ma[A[*g[i].begin()]]=i;
	}
	FOR(i,1,N-1){
		if(g[i].empty()) continue;
		if(valid[A[*g[i].begin()]]==1) continue;
		ll bg=*g[i].begin();
		ll ne=0;
		if(bg%2==0) ne=bg-1;
		else ne=bg+1;
		g[i].erase(bg);
		g[ma[A[ne]]].erase(ne);
		ans+=1;
		al+=2;
	}
	ans+=N-al;
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
1
3
1 1 1 3 1 3

3
*/