P1525 [NOIP2010 提高组] 关押罪犯 && P1559 运动员最佳匹配问题 && P3386 【模板】二分图最大匹配 day11

非常牛逼啊 这道题 先是像krusal一样 把边排序 然后相当于染色 要是染色失败 那就直接输出就好了 因为这就是最小最大值了 但是我最开始染色根本就没考虑啥 直接赋值1 2 来染 非常傻逼

然后就想到并查集 并查集非常牛逼啊 就相当于你把两个分类了 可是没有急着染色 

而且最牛逼的我还学到了 并查集要是语句里有些find 和 p【】等价 但是用find可以规避MLE

因为每次find 都会路径压缩一次 非常牛逼啊！

#include 
using namespace std;
const int N = 1e5+10;
const int M = 1e4+10;
const int mod = 998244353;
#define int long long
#define endl 'n'
#define Endl 'n'
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int n,m,p[N],q[N];
struct e{
    int a,b,w;
    bool operator < (const e&W)const{
        return w>W.w;
    }
}e[N];
int find(int x){
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)p[i]=i;
    for(int i=0;i>a>>b>>w;
        e[i]={a,b,w};
    }
    sort(e,e+m);
    for(int i=0;i 
 感觉n<=20随便爆搜都能过的 最后加了剪枝才过
 
剪枝策略就是 你把最大值搞出来 不管是否匹配 然后就会有递归的时候 要是开的很屎
 
就可以通过 后面的最优解+前面开的屎 直接pass掉 感觉这个剪枝没啥含金量啊！
 
#include 
using namespace std;
const int N = 22;
const int M = 1e4+10;
const int mod = 998244353;
#define int long long
#define endl 'n'
#define Endl 'n'
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int n,p[N][N],q[N][N],s[N],sum[N],ans=-2e9;
void dfs(int step,int k){
    if(step==n+1){ans=max(ans,k);return;}
    if(k+(sum[n]-sum[step-1])<=ans)return;
    for(int i=1;i<=n;i++){
        if(!s[i]){
            s[i]=true;
            dfs(step+1,k+p[step][i]*q[i][step]);
            s[i]=false;
        }
    }
}
signed main(){
    fast
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>p[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>q[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        int temp=-inf;
        for(int j=1;j<=n;j++)temp=max(temp,p[i][j]*q[j][i]);
        sum[i]=temp;
    }
    for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
    dfs(1,0);
    cout<
 
 贴个模板题 我真的有在好好训练啊！！！
 
#include 
using namespace std;
const int N = 5e4+10;
const int M = 1e4+10;
const int mod = 998244353;
#define int long long
#define endl 'n'
#define Endl 'n'
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int n,m,k,h[N],e[N<<1],ne[N<<1],idx,match[N<<1];
bool st[N<<1];
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int find ( int  x){
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        if(!st[j]){
            st[j]=true;
            if(!match[j]||find(match[j])){
                match[j]=x;
                return true;
            }
        }
    }
    return false;
}
signed main(){
    fast
    cin>>n>>m>>k;
    memset(h,-1,sizeof h);
    for(int i=1;i<=k;i++){
        int a,b;cin>>a>>b;
        add(a,b);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        memset(st,false,sizeof st);
        if(find(i))ans++;
    }
    cout<