P1199 三国游戏

题解

这是一道贪心题

 

 

 

代码

#include<bits/stdc++.h>

using namespace std;

int cnt,n,mp;
bool vis[1000010];

struct node
{
    int x;
    int y;
    int w;
}jiang[1000010];

bool cmp(node x,node y)
{
    return x.w >y.w ;
}

int main()
{
    scanf("%d",&n);
    cnt=0;
    
    for(int i=1;i<=n-1;i++)
      for(int j=i+1;j<=n;j++)
      {
          scanf("%d",&mp);
          jiang[++cnt].w =mp;
        jiang[cnt].x =i;
        jiang[cnt].y =j;
      }
    
    sort(jiang+1,jiang+cnt+1,cmp);
    
    int flag=0;
    
    vis[jiang[1].x ]=1;
    vis[jiang[1].y ]=1;
    for(int i=2;i<=cnt;i++)
    {
        if(vis[jiang[i].x] ||vis[jiang[i].y ])
        {
            printf("1\n");
            printf("%d\n",jiang[i].w );
            return 0;
        }
        else
        {
            if(!vis[jiang[i].x] ) vis[jiang[i].x]=1;
            if(!vis[jiang[i].y] ) vis[jiang[i].y]=1;
            
        }
    }
    
    
}