[生成树][treeDP][图论] 最小度限制生成树 POJ1639 Picnic Planning

思路全在论文里，实现的话费了点功夫。。感觉写这种复杂一点的题，最好还是先把需要用到的变量都写出来，需要的操作都列出来，不然反复修改会浪费很多时间。

需要注意的错误只发现了一个就是在枚举加度的时候可能会出现没边可删的情况（我也不知道为什么），然后这时候我的代码就开始跑环。。因为每次都会新加入一条边，不删边的话必定在树上形成环。后来的策略是一旦当前的操作不再使得生成树变小，那就直接break，因为显然他之后也不会再变小，而且可能之后会出现跑环，而这之前我的代码都是正确的，这样既可以剪枝又可以避免坑。。。

自己实现的方法还是有些暴力，由于用了矩阵存图基本上V²了。。不过好在数据很水很小，写的正确即可过。


//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#define eps (1e-9)
using namespace std;
typedef long long LL;
const int maxn=20+5;
const int MOD=1e9+7;
const int INF=0x4f4f4f4f;

void read(int &x)
{
    char ch = getchar();
    x = 0;
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (; ch >='0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
}
map mp;
int u[405],v[405],w[405];
int istree[maxn][maxn];
int G[maxn][maxn];
int cnt,m,n,k,mst,root;

int p[maxn],e[400];
bool cmp(int i,int j){return w[i]>a>>b>>tw;
        if(mp[a]==0)
            mp[a]=++cnt;
        if(mp[b]==0)
            mp[b]=++cnt;
        if(a=="Park")
            root=mp[a];
        if(b=="Park")
            root=mp[b];
        G[mp[a]][mp[b]]=tw;
        G[mp[b]][mp[a]]=tw;
        u[i]=mp[a],v[i]=mp[b],w[i]=tw;
    }
    scanf("%d",&k);
    ocnt=cnt;
    Kruskal();
    int tmst=mst;
    for (int i=1;i<=ocnt;i++)
    {
        mini[i]=INF;
        int mv=0;
        for (int j=1;j<=ocnt;j++)
        {
            if(G[root][j]&&find(j)==i&&mini[i]>G[root][j])
            {
                mini[i]=G[root][j];
                mv=j;
            }
        }
        if(mini[i]!=INF)
        {
            istree[root][mv]=istree[mv][root]=1;
            tmst+=mini[i];
        }
    }
    int ans=tmst;
    for (int i=cnt;i<=k;i++)
    {
        best[root]=0;
        memset(bestn,0,sizeof(bestn));
        dfs(root,-1);
        int mi=INF,bv=0,du=0,dv=0;
        for (int i=1;i<=ocnt;i++)if(!istree[root][i]&&G[root][i]&&G[root][i]-best[i]

一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

发表回复 取消回复

发表回复取消回复