首页 > 代码库 > topcoder srm 693 div1 -3

topcoder srm 693 div1 -3

2024-09-24 11:57:40   215人阅读

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];	}};

　　

topcoder srm 693 div1 -3


联系
我们