acm-ACM HDU1879继续畅通工程 提交RE.求各路大神帮忙看一下哪儿错了

问题描述

ACM HDU1879继续畅通工程 提交RE.求各路大神帮忙看一下哪儿错了

题目大意:
求最小生成树的权值和,并输出。已经修建的路(已经连上的边)是不会算入到最后的ANS中。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 );随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态,每行给4个正整数,分别是两个村庄的编号(从1编号到N),此两村庄间道路的成本,以及修建状态:1表示已建,0表示未建。

当N为0时输入结束。

Sample Input

3
1 2 1 0
1 3 2 0
2 3 4 0
3
1 2 1 0
1 3 2 0
2 3 4 1
3
1 2 1 0
1 3 2 1
2 3 4 1
0

Sample Output

3
1
0

我的思路:就是把创建部分稍微做点修改,改成如果修建过,则此边的权值为0。
我出现的问题:我是初学PRIM,算法是自己根据定义写的,可能比较毛糙,问题不知道出在哪儿。提交上去是RE,(ACCESS_VIOLATION)。我仔细看过数组是否越界,我并没有看出有越界的地方。
上一道HDU1863畅通工程,同类型的题目我用这个算法AC了。
所以现在不知道错误在哪儿,请求各位指点一二。

下面是我的代码,运行没有问题,样例也通过。。。
#include "iostream"
#include "algorithm"
using namespace std;
typedef struct
{
int from;
int to;
int value; //权值
bool used; //是否被标记过
bool now; //是否为待选直接相邻边
}Edge;
Edge e[105];
bool V[105];//顶点集。
const int Inf=10000000;
bool Mycmp(Edge A,Edge B)
{
return A.value<B.value;
}

void Create(int n)
{
int i,length=0,Q;

for(i=0;i
V[i]=false;
for(i=0;i
e[i].used=false;
for(i=0;i
{
cin>>e[i].from>>e[i].to>>e[i].value>>Q;
if(Q==1)
e[i].value=0;
}
stable_sort(e,e+n,Mycmp);

}
void Find(int n,int from) //用来找出和这个顶点直接相连的边。
{
int i;
for(i=0;i<n;i++)
{
if(e[i].used==false&&(e[i].from==from||e[i].to==from))

{
if(V[e[i].from]==true&&V[e[i].to]==true) //用于判断是否会构成环
continue;
e[i].now=true;
}
}

}
void Clear(int n)
{
for(int i=0;i<n;i++)
e[i].now=false;

}

int Prim(int n,int m)
{
int i,from,to,j,jindex,value,min,ans=0;
from=e[0].from;

to=e[0].to;
e[0].used=true;
V[from]=true;

V[to]=true;
ans+=e[0].value;
for(i=1;i
{
Clear(n);
for(j=1;j
{
if(V[j]==true) //顺着顶点,把边挑选出来
{
Find(n,j);
}
}
min=Inf;
jindex=-1;
for(j=0;j
{
if(e[j].now==true)
{
if(min>e[j].now)
{
min=e[j].now;
jindex=j;
}
}
}

    e[jindex].used=true;    //找到合适的边
    V[e[jindex].from]=true;
    V[e[jindex].to]=true;
    ans+=e[jindex].value;

}
return ans;

}

int main()
{
int n,m,ans,t,flag;
while(cin>>m)
{

    if(m==0)    //题意,如果为0则跳出
        break;
    n=m*(m-1)/2;
  Create(n);
 ans=Prim(n,m);
    cout<<ans<<endl;
}
return 0;

}

解决方案

算法有问题

 /*
hdu1879
2013-03-18 15:25:50    Accepted    1879    406MS    360K    1188 B
典型的最小生成树,在做并查集时做的这道题,
所以使用并查集实现的克鲁斯卡尔算法
*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

struct node {
    int start ,end,expense,flag;
}data[5005];

int father[105];
void make_set(int n)
{
    for(int i=1;i<=n;i++)
        father[i]=i;
}
int find_set(int x)
{
    if(x^father[x])
        father[x]=find_set(father[x]);
    return father[x];
}
int union_set(int x,int y)
{
    x=find_set(x);
    y=find_set(y);
    if(x==y)
        return 0;
    father[x]=y;
    return 1;
}
bool cmp(node a,node b)
{
    return a.expense<b.expense;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(!n)
            break;
        make_set(n);
        int ans=0;
        int m=(n-1)*n/2;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d%d",&data[i].start,&data[i].end,&data[i].expense,&data[i].flag);
            if(data[i].flag)//当道路修通时,规定一节点为另一节点的父亲
                father[data[i].start]=data[i].end;
        }
        sort(data,data+m,cmp);//按道路的花费升序排列

        //在不构成环的前提下,选择最短的边,有贪心的思想
        for(int i=0;i<m;i++)
        {
            if(union_set(data[i].start,data[i].end))
                ans+=data[i].expense;
        }
        printf("%dn",ans);
    }
    return 0;
}
时间: 2016-03-16
Tags: acm, prim

acm-ACM HDU1879继续畅通工程 提交RE.求各路大神帮忙看一下哪儿错了的相关文章

alert-点击提交按钮的时候没有反应,麻烦大神帮忙看一下是什么问题

问题描述 点击提交按钮的时候没有反应,麻烦大神帮忙看一下是什么问题 <!-- .STYLE1 {color: #FF0000} --> ? function check() { if (document.FORM10.zh.value=="") { alert("用户名必填!"); document.FORM10.zh.focus(); return false; } FORM10.submit(); } 信息录入 账号: 密码: 姓名: 科室: &qu

gradle-向andriod studio中导入eclipse工程出错,求大神帮忙!!

问题描述 向andriod studio中导入eclipse工程出错,求大神帮忙!! Error:Could not find any version that matches com.android.tools.build:gradle:1.0.0.+. 第一次用andriod studio,不是很熟悉,按照网上的要求一步步操作,但是要出如上的错误,不知道怎么回事. 解决方案 问问3434嗡嗡嗡恶嗡嗡嗡 解决方案二: 问问3434嗡嗡嗡恶嗡嗡嗡 解决方案三: 问问3434嗡嗡嗡恶嗡嗡嗡 解决方

使用ext提交表单出错,求大神帮忙

问题描述 使用ext提交表单出错,求大神帮忙 jsp页面代码如下: <%@ page language="java" contentType="text/html; charset=utf-8" pageEncoding="utf-8"%> <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.or

myeclipse-运行java工程出现以下错误,大神们帮忙看一下吧,给点建议!

问题描述 运行java工程出现以下错误,大神们帮忙看一下吧,给点建议! 求各位指点迷津!我是用的myeclipse下tomcat6运行,可以跳出index.jsp登录页面,但是后台打印会有以上的错误.而且当我输入登录账号密码时又出现这种错误: 解决方案 把代码贴出来看看,造成这个异常的可能性很多 解决方案二: 你可以参考这篇博客的解决方案:http://blog.csdn.net/jaune161/article/details/18361421 解决方案三: 什么操作造成,在那一步的代码上找原

status-jsp页面向数据库提交数据报了一个错,求大神。

问题描述 jsp页面向数据库提交数据报了一个错,求大神. HTTP Status 400- type>Status report message descritionThe request sent by the client was syntactically incorrect. 解决方案 1.语义有误,当前请求无法被服务器理解.除非进行修改,否则客户端不应该重复提交这个请求. 2.请求参数有误. http://tool.oschina.net/commons?type=5 相关文章 将一个

c++的问题-ACM北大POJ_1376代码提交一直WA,求大神看看哪里错了?呜呜

问题描述 ACM北大POJ_1376代码提交一直WA,求大神看看哪里错了?呜呜 #include #include #include using namespace std; bool Map[55][55]; bool vis[55][55][4]; //[4] 四个directions,坐标和方向都相同时不能同时经过该点两次: int M,N; bool flag=false; //找到路径置为true: typedef struct { int x,y; //坐标: int time; /

请教各位算法大神,acm一道题:赋权无向图的最小权值遍历用什么算法(存在负权值)?

问题描述 请教各位算法大神,acm一道题:赋权无向图的最小权值遍历用什么算法(存在负权值)? 1C 如题,问题是这样的:有一赋权无向连通图,可以从任意一结点出发,求遍历所有结点的最小权值路线.结束点也是任意的,每个节点也没有访问次数的限制,但必须每个节点都要被访问到.,想问一下用什么算法呢? 解决方案 可以参考djstera算法,求最短路径~借鉴其中的标记功能,只不过结束状态标志是所有节点均已遍历. 解决方案二: 可以参考djstera算法,求最短路径~借鉴其中的标记功能,只不过结束状态标志是所

字符-一道acm水题 all in all 一直找不出错误 求大神解答

问题描述 一道acm水题 all in all 一直找不出错误 求大神解答 描述字符串s和t均由字母组成,若在t中除去一些字母能够得到s,我们就说s是t的一个子串.比如abc就是acbefc的子串(acbefc去掉第二.第四.第五个字符后就得到abc)输入有若干组输入数据,每组一行,分别为字符串s和t,s与t之间用空格隔开输出对于一组s与t,若s是t的子串,则输出Yes,否则输出No 样例输入sequence subsequence abc acb VERDI vivaVittorioEmanu

c++问题-在acm上刷题老是通不过,求大神指点一二,到底问题出在哪里。不胜感激!!!

问题描述 在acm上刷题老是通不过,求大神指点一二,到底问题出在哪里.不胜感激!!! #include #include using namespace std; int main() { int T; int k,t=0; int i, j, n1, n2; char a[1010], b[1010], c[1015]; string d[20], e[20], f[20]; cin>>T; for(k=1; k<=T; k++) { cin>>a>>b; d[