1 条题解

  • 0
    @ 2025-10-8 17:10:09
    #include<bits/stdc++.h>
    using namespace std;
    const int M=2e7+5e6+10,N=5e3+10;
    int n;
    int h[M],nt[M],w[M],g[M],id=1;
    struct ll{
    	int x;
    	int y;
    	int z;
    }a[N];
    pair<int,int> match[N];
    int st[N];
    int ans;
    inline void add(int a,int b,int c){
    	g[id]=b;
    	w[id]=c;
    	nt[id]=h[a];
    	h[a]=id++;
    }//链式前向星建边
    int s[N];
    inline bool dfs(int num,int c){
    	for(register int i=s[num];~i;i=nt[i]){
    		int j=g[i];
    		if(!st[j]){
    			st[j]=1;
    			if(!match[j].first||dfs(match[j].first,match[j].second)){
    				match[j]={num,c};
    				s[num]=i;
    				return 1;
    			}
    		}
    	}
    	return 0;
    }//带权二分图最大匹配,不会的请自行学习,这里不过多解释
    int mi,mx;
    inline int cmp(ll a,ll b){
    	return a.z>b.z;
    }
    inline int read() {
    	register int x=0;
    	register char ch=getchar();
    	while(isdigit(ch)){
    		x=(x<<3)+(x<<1)+ch-48;
    		ch=getchar();
    	}
    	return x;
    }
    signed main()
    {
    	cin>>n;
    	memset(h,-1,sizeof h);	
    	for(int i=1;i<=n;i++){
    		cin>>a[i].x>>a[i].y>>a[i].z;
    	}
    	sort(a+1,a+n+1,cmp);//利用了贪心的思想,排序
    	for(register int i=1;i<=n;i++){
    		for(register int j=a[i].x;j<a[i].y;j++){
    			add(i,j,a[i].z);//建边
    		}
    	}
    	for(register int i=1;i<=n;i++){
    		s[i]=h[i];//优化
    	}
    	for(register int i=1;i<=n;i++){
    		memset(st,0,sizeof st);
    		dfs(i,a[i].z);//对每个点进行匹配
    	}
    	for(register int i=1;i<=n;i++){
    		ans+=match[i].second;//加上选上的边权
    	}
    	cout<<ans;
    	return 0;
    }
    
    • 1

    【带权二分图最大匹配】[ONTAK2015] Bajtman i Okrągły Robin

    信息

    ID
    5941
    时间
    10000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者