1 条题解
-
0
#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
信息
- ID
- 5941
- 时间
- 10000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者