题解：P12026 [USACO25OPEN] Compatible Pairs S

· · 题解

咋全都是拓扑啊，给出一种更加无脑（数据结构学傻了导致的）做法。

看到做匹配，直接想到网络流。但是我只会二分图匹配。所以我们要先证明，如果给可以消除的点连边，最后连出来的都是二分图。

这个是显然的，首先扔掉自环，这个最后考虑就好了。

然后考虑如果出现一个环 a,b,c，那么就要求 a+b,a+c,b+c 只有两种不同的数。显然这是不可能的。至于环更长的情况也不可能。

然后我们就可以直接上网络流跑二分图匹配了！

荣获最劣解第一页。

网络流这玩意很玄学，虽然理论复杂度很高，但是实际情况下你可以相信他的常数。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
mt19937 rnd(time(0));
const int mod=998244353,inf=0x3f3f3f3f3f3f3f3f;
const int N=2e5+10,M=2e5+10;
int n,A,B;
int a[N],b[N];
map<int,int>mp;
vector<int>e[N];
int col[N];
void dfs(int x)
{
    for ( auto v:e[x] )
        if(!col[v]){col[v]=3-col[x];dfs(v);}
        else assert(col[v]!=col[x]);
}
namespace FLOW{
    vector<pair<int,int>>e[N];
    vector<int>id[N];
    void add(int u,int v,int w)
    {
//      cerr << "add: " << u << " " <<v << " " <<w  << endl;
        id[u].push_back(e[v].size());
        id[v].push_back(e[u].size());
        e[u].push_back({v,w});
        e[v].push_back({u,0});
    }
    int dep[N],gap[N];
    const int S=0,T=N-5;
    queue<int>q;
    void bfs()
    {
        memset(dep,0x3f,sizeof(dep));
        dep[T]=0,q.push(T);
        while(!q.empty())
        {
            int x=q.front();q.pop();
            gap[dep[x]]++;
            for ( auto v:e[x] )if(dep[v.first]>dep[x]+1)dep[v.first]=dep[x]+1,q.push(v.first);
        }
    }
    int dfs(int x,int flow)
    {
        if(x==T)return flow;
        int used=0;
        for ( int i = 0 ; i < e[x].size() ; i++ )
        {
            int v=e[x][i].first,w=e[x][i].second;
            if(!w||dep[v]!=dep[x]-1)continue;
            int f=dfs(v,min(w,flow-used));
            used+=f;
            e[x][i].second-=f;
            e[v][id[x][i]].second+=f;
            if(used==flow)return used;
        }
        gap[dep[x]]--;
        if(!gap[dep[x]])dep[S]=T+5;
        dep[x]++;
        gap[dep[x]]++;
        return used;
    }
    void solve()
    {
        bfs();
        int maxflow=0;
        while(dep[S]<T+5)
        {
            maxflow+=dfs(S,inf);
//          cerr << maxflow << endl;
        }
        for ( auto i:e[S] )
        {
            int v=i.first,w=i.second;
            if(b[v]+b[v]==A||b[v]+b[v]==B)maxflow+=w/2;
        }
        for ( auto i:e[T] )
        {
            int v=i.first,w=i.second;
            if(b[v]+b[v]==A||b[v]+b[v]==B)maxflow+=(a[v]-w)/2;
        }
        cout << maxflow << endl;
    }
    //todo
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >>n >> A>>B;
    for ( int i = 1 ; i <= n ; i++ )
    {
        cin >> a[i] >> b[i];
        mp[b[i]]=i;
    }
    for ( int i = 1 ; i <= n ; i++ )
    {
        if(mp[A-b[i]]&&mp[A-b[i]]!=i)
//          cerr << "add " << i << " " << mp[A-b[i]] << endl,
            e[i].push_back(mp[A-b[i]]);
        if(mp[B-b[i]]&&mp[B-b[i]]!=i)
//          cerr << "add " << i << " " << mp[B-b[i]] << endl,
            e[i].push_back(mp[B-b[i]]);
    }
    for ( int i = 1 ; i <= n ; i++ )if(!col[i]){col[i]=2;dfs(i);}
    for ( int i = 1 ; i <= n ; i++ )
    {
        if(col[i]==1)FLOW::add(FLOW::S,i,a[i]);
        else FLOW::add(i,FLOW::T,a[i]);
        if(col[i]==1)for ( auto v:e[i] )FLOW::add(i,v,inf);
    }
    FLOW::solve();
    return 0;
}