首页 > 代码库 > HDU 4948

HDU 4948

题目大义:

  给一张图,任意两点间有单向边,找出一种方案,使得每个新入队的点与队中的点距离<=2。

题解:

  贪心,从最后入队点开始反向插入,每次找出最大入度的点入队。

  只需证明最大入度点A与所有未入队的点距离<=2

    每次加入最大入度点A,设未入队的B集与A距离为1,假设若有未入队的点C与A距离>2,则必有A->C,B->C,则有C入度>A,矛盾!

  故恒有解

代码:

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))using namespace std;struct City{    int out,res;}city[505];int n;char p;bool cmp(City x, City y){    return x.out<y.out;}int main(){    while(scanf("%d",&n)!=EOF && n)    {        for(int i=0; i<n; i++)        {            city[i].res=i;            city[i].out=0;        }        for(int i=0; i<n; i++)        {            getchar();            for(int j=0; j<n; j++)            {                scanf("%c",&p);                if(p==1) city[i].out++;            }        }        sort(city,city+n,cmp);        for(int i=n-1; i>0; i--)            printf("%d ",city[i].res+1);        printf("%d\n",city[0].res+1);    }    return 0;}
View Code

 

HDU 4948