首页 > ACM题库 > HDU-杭电 > HDU 3970-Harmonious Set-图-[解题报告]HOJ
2015
04-14

HDU 3970-Harmonious Set-图-[解题报告]HOJ

Harmonious Set

问题描述 :

For a giving integer n ( n > 0 ) , the set Sn consists of the non negative integers less than n. For example:S5 = {0,1,2,3,4}. A subset of Sn is harmonious if and only if the sum of its elements is a multiply of n. Now your task is easy. For a given n , you should find the number of harmonious subset of Sn.

输入:

There is a number C in the first line , meaning there are C cases . C is guaranteed no more than 300.

Then C cases below. Each case is a positive integer n in a single line. n is not greater than 10^9.

输出:

There is a number C in the first line , meaning there are C cases . C is guaranteed no more than 300.

Then C cases below. Each case is a positive integer n in a single line. n is not greater than 10^9.

样例输入:

5
1
2
3
10
1000

样例输出:

2
2
4
104
618918635

/*代码慢慢敲,教训*/

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define size 1010
#define INF 99999999
int n,m,a,b,d,p,s,t;
int S[size],dist[size],value[size];
int map[size][size],cos[size][size];
void dijkstra(int u0)
{

        for(int i=1;i<=n;i++)
        {
                dist[i]=map[u0][i];
                value[i]=cos[u0][i];
                S[i]=0;
        }
        S[u0]=1;
        for(int i=1;i<n;i++)
        {
                int min=INF,v=u0;
                for(int j=1;j<=n;j++)
                {
                        if(min>dist[j] && !S[j])
                        {
                                v=j,min=dist[j];
                        }
                }
                S[v]=1;
                for(int j=1;j<=n;j++)
                {
                        if(!S[j] && map[v][j]<INF)
                        {
                                if(dist[j]>dist[v]+map[v][j])
                                {
                                        dist[j]=dist[v]+map[v][j];
                                        value[j]=value[v]+cos[v][j];
                                }
                                else if(dist[j]==dist[v]+map[v][j])
                                {
                                        if(value[j]>value[v]+cos[v][j])
                                        {
                                                value[j]=value[v]+cos[v][j];
                                        }
                                }
                        }

                }
        }
        printf("%d %d\n",dist[t],value[t]);
}
int main()
{
        while(~scanf("%d%d",&n,&m)&&n+m)
        {
                for(int i=1;i<=n;i++)
                    for(int j=1;j<=n;j++)
                    {
                            map[i][j]=INF;
                            cos[i][j]=INF;
                    }
                for(int i=0;i<m;i++)
                {
                        scanf("%d%d%d%d",&a,&b,&d,&p);
                        {
                                if(map[a][b]>d)
                                {
                                        map[a][b]=map[b][a]=d;
                                        cos[a][b]=cos[b][a]=p;
                                }
                                else if(map[a][b]==d)//该死的等于,代码要慢慢敲,经验
                                {
                                        if(cos[a][b]>p)
                                        {
                                                cos[a][b]=cos[b][a]=p;
                                        }
                                }
                        }
                }
                scanf("%d%d",&s,&t);
                dijkstra(s);
        }
        return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/u011368360/article/details/16607707


  1. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish