首页 > ACM题库 > HDU-杭电 > HDU 4781-Assignment For Princess-图-[解题报告]HOJ
2015
09-17

HDU 4781-Assignment For Princess-图-[解题报告]HOJ

Assignment For Princess

问题描述 :

  Long long ago, in the Kingdom Far Far Away, there lived many little animals. And you are the beloved princess who is marrying the prince of a rich neighboring kingdom. The prince, who turns out to be a handsome guy, offered you a golden engagement ring that can run computer programs!
  The wedding will be held next summer because your father, the king, wants you to finish your university first.
  But you did’t even have a clue on your graduation project. Your terrible project was to construct a map for your kingdom. Your mother, the queen, wanted to make sure that you could graduate in time.
  Or your wedding would have to be delayed to the next winter. So she told you how your ancestors built the kingdom which is called the Roads Principle:

  1. Your kingdom consists of N castles and M directed roads.
  2. There is at most one road between a pair of castles.
  3. There won’t be any roads that start at one castle and lead to the same one.
  She hoped those may be helpful to your project. Then you asked your cousin Coach Pang (Yes, he is your troubling cousin, he always asks you to solve all kinds of problems even you are a princess.), the Minister of Traffic, about the castles and roads. Your cousin, sadly, doesn’t have a map of the kingdom. Though he said the technology isn’t well developed and it depends on your generation to contribute to the map, he told you the Travelers Guide, the way travelers describe the amazing road system:
  1. No matter which castle you start with, you can arrive at any other castles.
  2. Traveling on theM roads will take 1, 2, 3, … ,M days respectively, no two roads need the same number of days.
  3. You can take a round trip starting at any castle, visiting a sequence of castles, perhaps visiting some castles or traveling on some roads more than once, and finish your journey where you started.
  4. The total amount of days spent on any round trip will be a multiple of three.
  But after a month, you still couldn’t make any progress. So your brother, the future king, asked your university to assign you a simpler project. And here comes the new requirements. Construct a map that satisfies both the Roads Principle and the Travelers Guide when N and M is given.
  There would probably be several solutions, but your project would be accepted as long as it meets the two requirements.
Now the task is much easier, furthermore your fiance sent two assistants to help you.
  Perhaps they could finish it within 5 hours and you can think of your sweet wedding now.

输入:

  The first line contains only one integer T, which indicates the number of test cases.
  For each test case, there is one line containing two integers N, M described above.(10 <= N <= 80, N+3 <= M <= N2/7 )

输出:

  The first line contains only one integer T, which indicates the number of test cases.
  For each test case, there is one line containing two integers N, M described above.(10 <= N <= 80, N+3 <= M <= N2/7 )

样例输入:

1
6 8

样例输出:

Case #1:
1 2 1
2 3 2
2 4 3
3 4 4
4 5 5
5 6 7
5 1 6
6 1 8
Hint
��The restrictions like N >= 10 will be too big for a sample. So the sample is just a simple case for the detailed formats of input and output, and it may be helpful for a better understanding. Anyway it won’t appear in actual test cases.

哎,第一次见给点数和边数,让按要求还原出有向图的。

要求概况一下:

1.强连通。

2.任意俩点直接之间只有一条有向边,自己和自己无边。

3.任意一个闭合回路权和%3为0。

4.每条边的权理论不同,而且是1,2,3..m

开始就想到必有一个大环1->2->3->…..n,n->1;  模拟比赛时.,没有往下想了。。

先添加边: i->i+1是权为I,之后从(n,n+1,n+2)中选一条添加N到1的权,使得闭环%3=0.

之后处理 剩下m-n条边,

:注意若 在 i—>j 附加边,则有w(i,j)%3==从i到j边权之和%3即可(容易证明)

枚举每条即可(n<80,m<n*n/7)。

#include<iostream>
#include<cstring>
using namespace std;
int n,m;
int mark[6400];
int vis[85][85];   
int main()
{
    int T;
    cin>>T;int ct=1;
    while(T--)
    {
        for(int i=0;i<=m;i++)
            mark[i]=0;
        memset(vis,0,sizeof(vis));
           cin>>n>>m;
        for(int i=1;i<n;i++)
        {
           // cout<<i<<" "<<i+1<<" "<<i<<endl;
            mark[i]=1;vis[i][i+1]=vis[i+1][i]=i;
        }
        int tei=0;
        for(int i=n;i<n+3;i++)
           if((n*(n-1)/2+i)%3==0)
           {
              //cout<<n<<" "<<1<<" "<<i<<endl;
              tei=i;
              mark[i]=1;
              vis[n][1]=vis[1][n]=i;
              break;
          }
       for(int i=n;i<=m;i++)
       {
           if(!mark[i])
           {
               int flags=0;
               for(int j=1;j<=n;j++)
               {

                for(int k=j+2;k<=n;k++)
                {

                    if(!vis[j][k]&&((k-j)*(j+k-1)/2)%3==i%3)
                    {
                        vis[j][k]=vis[k][j]=i;
                        mark[i]=1;
                        flags=1;
                        break;
                    }
                }
                if(flags)break;
               }
           }
       }
       bool flag=1;
       for(int i=1;i<=m;i++)
       {
           if(mark[i]==0)
             {
                 flag=0;break;
             }
       }
       cout<<"Case #"<<ct++<<":"<<endl;
       if(flag==0)
       cout<<-1<<endl;
       else
       {
           for(int i=1;i<=n;i++)
             for(int j=(i+1);j<=n;j++)
             {
                 if(vis[i][j]!=0&&!(i==1&&j==n))
                 {
                     cout<<i<<" "<<j<<" "<<vis[i][j]<<endl;
                 }
             }
            cout<<n<<" "<<1<<" "<<tei<<endl;
       }
    }
}

参考:http://blog.csdn.net/u011498819/article/details/38986419