首页 > ACM题库 > HDU-杭电 > hdu 2655 Counting Triangles-最小生成树-[解题报告]C++
2014
02-12

hdu 2655 Counting Triangles-最小生成树-[解题报告]C++

Counting Triangles

问题描述 :

There are many different points int xoy coordinate axes. Connect every two points with straight line. How many triangles can you find.

输入:

There are many test cases. Please process to end of file. First of each test case is an integer N (3 <= N <= 1000). Then N line follows, each line contains one unique point X, Y (-10000000 <= X, Y <= 10000000).

输出:

There are many test cases. Please process to end of file. First of each test case is an integer N (3 <= N <= 1000). Then N line follows, each line contains one unique point X, Y (-10000000 <= X, Y <= 10000000).

样例输入:

3
0 0
1 1
2 2
3
0 0
1 0
1 1

样例输出:

0
1

http://acm.hit.edu.cn/hoj/problem/view?id=2655

 

此题主要利用广搜,先筛素预处理4位整数,将4位数的每一位搜一次,将素数保存到queue中。

/*This Code is Submitted by billforum for Problem 2655 at 2012-01-30 12:27:42*/
#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;

struct point
{
        int wei[4];//保存每位的数字
        int num;//四位数的具体值
        int step;//记录改变的步数
        bool visit;//标记是否入队列
};

int pow(int x,int y)
{
        int ans=1;
        for(int i=1;i<=y;i++)
                ans=ans*x;
        return ans;
}
int main(int args,char **argv)
{
        int pr[10001],pn=0;
        bool flag[10001];
        int test,fp,lp,ans;
        point data[9000];
        bool f_ans=0;
        memset(flag,0,sizeof(flag));
        memset(pr,0,sizeof(pr));
        //筛素
        for(int i=2;i<10001;i++)
        {
                if(!flag[i]) pr[pn++]=i;
                for(int j=0;(j<pn)&&(i*pr[j]<10001);j++)
                {
                        flag[i*pr[j]]=1;
                        if(i%pr[j]==0) break;
                }
        }
        
        cin>>test;
        while(test--)
        {
                cin>>fp>>lp;
                ans=0;
                f_ans=0;  
            //初始化   
 for(int i=0;i<9000;i++)
        {
                int tmp;
                data[i].num=i+1000;
                tmp=data[i].num;
                data[i].step=0;
                data[i].visit=0;
                for(int j=3;j>=0;j--)
                {
                        data[i].wei[j]=tmp%10;
                        tmp=tmp/10;
                }
        }
                point f,l;
                int ntmp;
                f.num=fp;
                f.step=0;
                f.visit=1;
                ntmp=fp;
                for(int j=3;j>=0;j--)
                {
                        f.wei[j]=ntmp%10;
                        ntmp=ntmp/10;
                }
                l.num=lp;
                ntmp=lp;
                l.step=0;
                l.visit=0;
                for(int j=3;j>=0;j--)
                {
                        l.wei[j]=ntmp%10;
                        ntmp=ntmp/10;
                }
                queue<point> list;
                list.push(f);
                while(!list.empty())
                {
                        point tmp=list.front();
                        if(tmp.num==l.num)
                        {
                                ans=tmp.step;
                                f_ans=1;
                                break;
                        }
//广搜
 for(int i=0;i<4;i++)
                        {
                                if(i==0)
                                {
                                        for(int j=1;j<10;j++)
                                {
                                        if(j==tmp.wei[i]) continue;
                                        else{
                                                int mid;
                                                mid=tmp.num+(j-tmp.wei[i])*pow(10,3-i);
                                                if((!flag[mid])&&(data[mid-1000].visit==0)) 
                                                 {
                                                        data[mid-1000].visit=1;
                                                        data[mid-1000].step=tmp.step+1;
                                                        data[mid-1000].num=mid;
                                                        list.push(data[mid-1000]);
                                                 }
                                            }
                                }
                                }
                                else{
                                for(int j=0;j<10;j++)
                                {
                                        if(j==tmp.wei[i]) continue;
                                        else{
                                                int mid;
                                                mid=tmp.num+(j-tmp.wei[i])*pow(10,3-i);
                                                if((!flag[mid])&&(data[mid-1000].visit==0)) 
                                                 {
                                                        data[mid-1000].visit=1;
                                                        data[mid-1000].step=tmp.step+1;
                                                        data[mid-1000].num=mid;
                                                        list.push(data[mid-1000]);
                                                 }
                                            }
                                }
                                    }
                                }
                                list.pop();
                        }
                
                if(f_ans==1) cout<<ans<<endl;
                
        }
        return 0;
}

 

解题转自:http://www.cnblogs.com/wuzhibin/archive/2012/01/30/prime_path.html


  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }