首先说说讨论区的数据，真是水。。结果我都正确，问题是提交WA了。
然后就是讨论区竟然还有说某某数据应该输出什么，结果他没输出这个，但是他A了，我输出了那个正确的结果，我还WA了。

再来说说思路：
  prim求出最小生成树，然后记录生成树的每一条边，对原先的图删除第i条边，求最小生成树，判断这个值是否与之前第一次的值相等，相等就不唯一，不相等继续循环。直到记录的边被枚举一遍。
 这样都不给我A 



贴WA代码，有兴趣者看之。我就想问一问大家，我还能不能快乐的在田野上奔跑？

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;

#define MAX 0xffffff
int map[10000][10000],low[10000],vis[10000]={0};
int n,m;
typedef struct data
{
 int st,et;
}data;
data plow[10000];
vector<data> G;
int ok;
int gt=0;
int count=0;
int prim()
{  
   
   int pos=1,minn;
   int weight=0;
   count=0;
   memset(vis,0,sizeof(vis));
   vis[pos]=1;
   for(int i=1;i<=n;i++)
      if(i!=pos)
        {low[i]=map[pos][i];
         plow[i].st=pos;
         plow[i].et=i;
        }
   for(int i=0;i<n-1;i++)
    {   
        minn=MAX;
         for(int j=1;j<=n;j++)
         {
             if(minn>low[j]&&!vis[j])
                {minn=low[j];
                  pos=j;
                }   
         }
       weight+=minn;  
       vis[pos]=1;  
      if(ok)
      {G.push_back((data){plow[pos].st,plow[pos].et});     
      }
      if(minn<MAX)
        count++;
         for(int j=1;j<=n;j++)
            if(map[pos][j]<low[j]&&!vis[j])
            {
               low[j]=map[pos][j]; 
               plow[j].st=pos;
               plow[j].et=j;
            }       
    } 
   
    return weight;
}

int main()
{
freopen("1.txt","r",stdin);
freopen("2.txt","w",stdout);
 int T,x,y,z,flag;
 scanf("%d",&T);
 while(T--)
 {  
    count=0;
    gt=0;
    ok=1;
    scanf("%d%d",&n,&m);
 
    for(int i=0;i<=n;i++)
      for(int j=0;j<=n;j++)
          map[i][j]=MAX;
    for(int i=0;i<m;i++)
     {  scanf("%d%d%d",&x,&y,&z);
       if(map[x][y]>z)
        map[x][y]=map[y][x]=z;
     }

     G.clear();
     int weight=prim();
     
   if(count!=n-1)
   {
    printf("Not Unique!\n");
    continue;
   
   }
          ok=0;
        for(int i=0;i<G.size();i++)
      {
         
        flag=0;
        data &e=G[i];
        int f=map[e.st][e.et];
        map[e.st][e.et]=map[e.et][e.st]=MAX;
        int now=prim();
        map[e.st][e.et]=map[e.et][e.st]=f;
        if(now==weight)
        {
          flag=1;
          break;
        }  
       }
   
     if(!flag)
     printf("%d\n",weight);
     else
     printf("Not Unique!\n");
   
 }
 
return 0; 
}

• Re:我被搞毛了。 (67) qq490456661 2014-07-28 09:24:06