1、给出一个$n$个顶点的无向带权图。其中顶点$i,i+1$之间存在边，$i,i+2$之间存在边。而且仅有这些边。现在删掉其中的一些边，剩下的边满足图仍然是2联通的情况下使得权值和最小？
思路：其实就是使得删掉的边的权值最大。对于第$i$和第$i+1$个顶点，2联通的两条路径一定经过了$e(i,i+1),e(i-1,i+1),e(i,i+2)$中的两个。也就是说这三条边最多只能删除其中的一条。现在从左向右依次考虑每个顶点。设$f[i]$表示顶点$i$之前的边已经全部考虑（不能删除$e(i-1,i+1)$了，因为它被当做是在$i$之前的边）。那么如果删掉了$e(i,i+1)$，那么后面就考虑顶点$i+1$；如果删除了$e(i,i+2)$，那么后面就直接考虑顶点$i+2$。因为$i+1$处其他的边不能再删除了。
#include <stdio.h>
#include <string>
#include <stack>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std; int f[105]; class BiconnectedDiv1
{
public:
int minimize(vector<int> w1,vector<int> w2)
{
const int n=(int)w1.size()+1;
int s=0;
for(int i=0;i<n-1;++i) s+=w1[i];
for(int i=0;i<n-2;++i) s+=w2[i]; for(int i=1;i<n-2;++i) {
f[i+1]=max(f[i+1],f[i]+w1[i]);
f[i+2]=max(f[i+2],f[i]+w2[i]);
}
return s-f[n-2];
}
};
2、构造一个二分图，左右的顶点个数相同但是不大于20且完美匹配恰好有$K$个。可以有重边
思路：构造思路是用3进制。
#include <stdio.h>
#include <string>
#include <stack>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std; class BipartiteConstruction
{
public:
vector<int> construct(int K)
{
vector<int> ans;
if(K==0)
{
ans.push_back(2);
ans.push_back(1);
ans.push_back(0);
return ans;
}
if(K==1)
{
ans.push_back(1);
ans.push_back(0);
return ans;
}
ans.push_back(20);
for(int i=0;i<19;++i) ans.push_back(i*20+i+1);
for(int i=2;i<20;++i) ans.push_back(i*20+i),ans.push_back(i*20+i),ans.push_back(i*20+i);
for(int i=19;i>=1;--i)
{
for(int j=0;j<K%3;++j) ans.push_back(i*20);
K/=3;
}
return ans; }
};