A. 一般图最小匹配
\(m\) 小于 \(\frac{n}{2}\) 所以对原数组排序后做差分，差分后的数不能选相邻的，设 \(f_{i,j,0/1}\) 表示前 \(i\) 个，选了 \(j\) 个，第 \(i\) 个选没选
直接 \(dp\) 求最小值就行
点击查看代码
#include<bits/stdc++.h>
const int maxn=5001;
using namespace std;
int n,m,a[maxn],d[maxn];
long long f[maxn][2501][2];int main()
{freopen("match.in","r",stdin);freopen("match.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);n--;for(int i=1;i<=n;i++)d[i]=a[i+1]-a[i];for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) f[i][j][0]=f[i][j][1]=1e15;f[1][1][1]=d[1],f[1][0][0]=0;for(int i=2;i<=n;i++){for(int j=0;j<=m;j++){f[i][j][0]=min(f[i][j][0],min(f[i-1][j][0],f[i-1][j][1]));if(j!=0)f[i][j][1]=min(f[i][j][1],f[i-1][j-1][0]+d[i]);
// cout<<i<<" "<<j<<" "<<f[i][j][1]<<" "<<f[i][j][0]<<endl;}}cout<<min(f[n][m][0],f[n][m][1]);return 0;
}
/*
4 1
2 4 7 38 3
9 2 3 12 11 7 6 5
*/
B. 重定向
大型分讨，我思路是考虑 \(1\) 和第一个 \(0\)，然后再向下细分是否考虑第一个使字典序变小的数，细节很多，5.8k代码，不建议观看
点击查看代码
#include<bits/stdc++.h>
#define int long long
const int maxn=1e6+10;
using namespace std;
int t,n,a[maxn],d[maxn],cnt,tem[maxn];
bool vis[maxn];signed main()
{
// freopen("test.in","r",stdin);
// freopen("ans.out","w",stdout);freopen("repeat.in","r",stdin);freopen("repeat.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>t;while(t--){int flag=0,flag2=0;cin>>n;fill(vis,vis+1+n,0);fill(d,d+1+n,0);for(int i=1;i<=n;i++){cin>>a[i];if(a[i]==0) flag2=1;vis[a[i]]=1;if(a[i]==1) flag=1;} if(!flag2){for(int i=1;i<=n;i++){if(a[i]>a[i+1]){a[i]=0;flag2=1;break;}}for(int i=1;i<=n-(flag2==0);i++)if(a[i]) cout<<a[i]<<" ";cout<<'\n';continue;}cnt=0;for(int i=1;i<=n;i++) if(!vis[i]) d[++cnt]=i;if(flag){
// cout<<"!";for(int i=1;i<=n;i++){if(a[i]==1){flag=0;break;}if(a[i]==0)break;}if(flag){for(int i=1;a[i]!=0;i++){if(a[i]>d[1]||(a[i]>a[i+1]&&a[i+1])) {flag=0;break;}}if(flag){
// cout<<"!";cnt=-1;for(int i=1;i<=n;i++) if(a[i]==1) a[i]=-1;d[0]=1;for(int i=1;i<=n;i++){if(a[i]==0) a[i]=d[++cnt];}for(int i=1;i<=n;i++){if(a[i]!=-1) cout<<a[i]<<" ";}cout<<'\n'; }else{
// cout<<"!";int temp=0;for(int i=1;a[i]!=0;i++){if(a[i]>d[1]&&a[i]>d[0]||(a[i]>a[i+1]&&a[i+1])){
// d[0]=a[i];tem[++temp]=i;
// break;}}
// cout<<temp<<endl;if(!temp){int s=0;for(int i=1;i<=n;i++)if(!a[i]) a[i]=-d[++s];for(int i=1;i<n;i++) if(abs(a[i])>abs(a[i+1])){d[0]=abs(a[i]);a[i]=0;sort(d,d+1+cnt);break;}int num=unique(d,d+1+cnt)-d-1;cnt=num;cnt=-1;if(!d[0])cnt++,a[n]=0;for(int i=1;i<=n;i++)if(a[i]<0) a[i]=d[++cnt];for(int i=1;i<=n;i++){if(a[i])cout<<a[i]<<" ";}cout<<'\n';}else{for(int i=1;i<=temp;i++)if(a[tem[i]]>a[tem[i]+1]){
// cout<<tem[i]<<" "<<tem[i]+1<<endl;temp=tem[i];d[0]=a[tem[i]];break;}a[temp]=-1;sort(d,d+1+cnt);int num=unique(d,d+1+cnt)-d-1;cnt=num;cnt=-1;for(int i=1;i<=n;i++){if(a[i]==0) a[i]=d[++cnt];}for(int i=1;i<=n;i++){if(a[i]!=-1)cout<<a[i]<<" ";}cout<<'\n'; }}}else{
// cout<<"!";int s=0;for(int i=1;i<=n;i++)if(!a[i]) a[i]=-d[++s];for(int i=1;i<n;i++) if(abs(a[i])>abs(a[i+1])){s=i;break;}int minn=1e9,sum=0; for(int i=1;i<=n;i++) if(a[i]<0) a[i]=0;for(int i=s+(s==0);i<=n;i++){if(a[i])minn=min(minn,a[i]);}while(!a[s])s++;for(int i=1;i<s;i++) {if(!a[i])sum++;if(minn<d[sum]) break;if(a[i]>minn){sum=0;break;}}
// cout<<minn<<endl;if(minn<d[sum]&&a[1]==1){
// cout<<"!";
// cout<<sum<<endl;for(int i=1;i<=n;i++){if(a[i]==minn) {d[0]=a[i];a[i]=-1;sort(d,d+cnt+1);break;}}cnt=-1;for(int i=1;i<=n;i++){if(!a[i])a[i]=d[++cnt];}for(int i=1;i<=n;i++){if(a[i]!=-1)cout<<a[i]<<" ";}cout<<'\n';}else{int s=0;for(int i=1;i<=n;i++)if(!a[i]) a[i]=-d[++s];for(int i=1;i<n;i++) if(abs(a[i])>abs(a[i+1])){d[0]=abs(a[i]);a[i]=0;sort(d,d+1+cnt);break;}int num=unique(d,d+1+cnt)-d-1;cnt=num;cnt=-1;if(!d[0])cnt++,a[n]=0;for(int i=1;i<=n;i++)if(a[i]<0) a[i]=d[++cnt];for(int i=1;i<=n;i++){if(a[i])cout<<a[i]<<" ";}cout<<'\n';}}}else{
// cout<<"!";int s=0;for(int i=1;i<=n;i++)if(!a[i]) a[i]=-d[++s];for(int i=1;i<n;i++) if(abs(a[i])>abs(a[i+1])){s=i;break;}int minn=1e9,sum=0; for(int i=1;i<=n;i++) if(a[i]<0) a[i]=0;for(int i=s+(s==0);i<=n;i++){if(a[i])minn=min(minn,a[i]);}while(!a[s])s++;for(int i=1;i<s;i++) {if(a[i]==minn) break;if(!a[i])sum++;if(minn<d[sum]) break;if(a[i]>d[sum+1]){sum=0;break;}}
// cout<<minn<<" "<<sum<<endl;if(minn<d[sum]&&a[1]==0){
// cout<<"!";for(int i=1;i<=n;i++){if(a[i]==minn) {d[0]=a[i];a[i]=-1;sort(d,d+cnt+1);break;}}cnt=-1;for(int i=1;i<=n;i++){if(!a[i])a[i]=d[++cnt];}for(int i=1;i<=n;i++){if(a[i]!=-1)cout<<a[i]<<" ";}cout<<'\n';}else{
// cout<<"!";int s=0;for(int i=1;i<=n;i++)if(!a[i]) a[i]=-d[++s];for(int i=1;i<n;i++) if(abs(a[i])>abs(a[i+1])){d[0]=abs(a[i]);a[i]=0;sort(d,d+1+cnt);break;}int num=unique(d,d+1+cnt)-d-1;cnt=num;cnt=-1;if(!d[0])cnt++,a[n]=0;for(int i=1;i<=n;i++)if(a[i]<0) a[i]=d[++cnt];for(int i=1;i<=n;i++){if(a[i])cout<<a[i]<<" ";}cout<<'\n';}}}return 0;
}
/*
3
2
1 0
2
0 1
1
11
9 7 5 11 0 3 4 6 8 1 2 */
C. 斯坦纳树
牛牛方法错误当且仅当存在一个点不是关键点但他连了大于等于三个关键点的边，这样会导致有的边按牛牛方法求被重复算
倒着删点，如果这个点有大于等于三条边，那他就会导致做法错误，然后把与他相连的边删了，如果有一个之前被删的会导致
错误的点在这个点被删后不会导致错误了，就把他删去，答案为1但且仅当不存在这样被删去的会导致错误的点，边权为零的
用并查集维护连通块
点击查看代码
#include<bits/stdc++.h>
const int maxn=3e5+10;
using namespace std;
int n,head[maxn],nxt[maxn<<1],to[maxn<<1],tot,p[maxn],fa[maxn],size[maxn],in[maxn];
int x[maxn],y[maxn],z[maxn],cnt,sum,son[maxn],ans[maxn];
bool vis[maxn];
set<int>q[maxn];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}void del(int x)
{ if(q[x].size()<=2&&!size[x]){sum--;int temp=0;for(auto i:q[x]) son[++temp]=i;q[x].clear();for(int i=1;i<=temp;i++){q[son[i]].erase(x);for(int j=i+1;j<=temp;j++){q[son[i]].insert(son[j]);q[son[j]].insert(son[i]); }}for(int i=1;i<=temp;i++) del(son[i]);}
}int main()
{freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<n;i++){int a,b,c;cin>>a>>b>>c;if(!c){a=find(a),b=find(b);if(a>b) swap(a,b);fa[b]=a;continue;}x[++cnt]=a,y[cnt]=b;}for(int i=1;i<n;i++) q[find(x[i])].insert(find(y[i])),q[find(y[i])].insert(find(x[i]));for(int i=1;i<=n;i++){cin>>p[i];p[i]=find(p[i]);size[p[i]]++;}for(int i=n;i>=1;i--){ans[i]=!sum;size[p[i]]--;if(!size[p[i]]) sum++,del(p[i]);}for(int i=1;i<=n;i++) cout<<ans[i];return 0;
}
/*
10
5 9 0
6 9 6
7 6 9
1 7 5
10 1 2
8 10 0
4 10 5
3 4 9
2 5 4
4 5 3 7 8 9 6 2 1 105
1 2 3
1 5 0
2 3 2
2 4 3
1 3 4 2 5
*/
