首页 > 搜索 > DFS搜索 > HDU 1658 Triangle -DFS-[解题报告] C++
2013
12-21

HDU 1658 Triangle -DFS-[解题报告] C++

Triangle

问题描述 :

A triangle is a basic shape of planar geometry. It consists of three straight lines and three angles in between. Figure 1 shows how the sides and angles are usually labeled.

Figure: Triangle





The values of a, b, c, , , and form a set of six parameters that fully define a triangle. If a large enough subset of these parameters is given, the missing ones can be calculated by using the formulas above.

You are to write a program that calculates the missing parameters for a given subset of the six parameters of a triangle. For some sets of parameters, it is not possible to calculate the triangle because either too few is known about the triangle or the parameters would lead to an invalid triangle. The sides of a valid triangle are greater than 0 and the angles are greater than 0 and less than . Your program should detect this case and output: "Invalid input." The same phrase should be output if more than the minimal set needed to compute the triangle is given but the parameters conflict with each other, e.g. all three angles are given but their sum is greater than .

Other sets of parameters can lead to more than one but still a finite number of valid solutions for the triangle. In such a case, your program should output: "More than one solution."

In all other cases, your program should compute the missing parameters and output all six parameters

输入:

The first line of the input file contains a number indicating the number of parameter sets to follow. Each following line consists of six numbers, separated by a single blank character. The numbers are the values for the parameters a, , b, , c, and respectively. The parameters are labeled as shown in figure 1. A value of -1 indicates that the corresponding parameter is undefined and has to be calculated. All floating-point numbers include at least eight significant digits.

输出:

Your program should output a line for each set of parameters found in the input file. If a unique solution for a valid triangle can be found for the given parameters, your program should output the six parameters a, , b, , c, , separated by a blank character. Otherwise the line should contain the phrase

"More than one solution." or

"Invalid input."

as explained above.

The numbers in the output file should include at least six significant digits. Your calculations should be precise enough to get the six most significant digits correct (i.e. a relative error of 0.000001 is allowed).

样例输入:

4
47.9337906847 0.6543010109 78.4455517579 1.4813893731 66.5243757656 1.0059022695
62.72048064 2.26853639 -1.00000000 0.56794657 -1.00000000 -1.00000000
15.69326944 0.24714213 -1.00000000 1.80433105 66.04067877 -1.00000000
72.83685175 1.04409241 -1.00000000 -1.00000000 -1.00000000 -1.00000000

样例输出:

47.933791 0.654301 78.445552 1.481389 66.524376 1.005902
62.720481 2.268536 44.026687 0.567947 24.587225 0.305110
Invalid input.
Invalid input.

#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
const int N = 101;
const int inf = 100000000;
char s1[N],s2[N];
bool flag[N];
bool chk[N];
int block[N],pre[N];
vector<int> vec[N];

struct Edge
{
    int v;
    int dis;
    bool flag;
    Edge* next;
}*pp,*adj[N],pool[2*N*N],*tree[N],*minEdge;
struct Node
{
    int from;
    int dis,at;
    Node() {}
    Node(int _from,int _at,int _dis)
    {
        from = _from;
        at = _at;
        dis = _dis;
    }
    bool operator < (const Node n) const
    {
        return dis > n.dis;
    }
};
void init()
{
    pp = pool;
    memset(adj,0,sizeof(adj));
    memset(tree,0,sizeof(tree));
}
void addedge(int u,int v,int dis,bool flag,Edge* adj[])
{
    pp->v = v;
    pp->dis = dis;
    pp->flag = flag;
    pp->next = adj[u];
    adj[u] = pp++;
}
int prim_heap(int start,int n)
{
    int ans = 0;
    priority_queue<Node> pq;
    pq.push(Node(-1,start,0));
    int k = 0;
    while(k < n && !pq.empty())
    {
        Node now = pq.top();
        pq.pop();
        if(flag[now.at])
            continue;
        flag[now.at] = true;
        ans += now.dis;
        if(now.from != -1)
        {
            addedge(now.at,now.from,now.dis,true,tree);
            addedge(now.from,now.at,now.dis,true,tree);
        }
        k++;
        for(Edge* p = adj[now.at]; p; p=p->next)
            if(!flag[p->v])
                pq.push(Node(now.at,p->v,p->dis));
    }
    return ans;
}
void dfs(int from,int now)
{
    flag[now] = true;
    pre[now] = from;
    for(Edge* p = tree[now]; p; p=p->next)
        if(!flag[p->v] && p->flag)
            dfs(now,p->v);
}
void calMinEdge(int now,int val)
{
    for(Edge* p = tree[now]; p; p=p->next)
        if(flag[p->v]  && p->flag)
        {
            flag[p->v] = false;
            if(p->dis > val)
            {
                minEdge = p;
                val = p->dis;
            }
            calMinEdge(p->v,val);
        }
}
int main()
{
    int m;
    scanf("%d",&m);
    init();
    map<string,int> mp;
    mp["Park"] = 0;
    for(int i=0; i<N; i++)
        vec[i].clear();
    int idx = 1,degree;
    for(int i=0; i<m; i++)
    {
        int dis;
        scanf("%s %s %d",s1,s2,&dis);
        if(mp.find(s1) == mp.end())
            mp[s1] = idx ++;
        if(mp.find(s2) == mp.end())
            mp[s2] = idx ++;
        int u = mp[s1], v = mp[s2];
        addedge(u,v,dis,true,adj);
        addedge(v,u,dis,true,adj);
    }
    scanf("%d",&degree);
    int n = idx; // n points 0 ~ n - 1
    int rem = 0,nb = 0;
    memset(chk,0,sizeof(chk));
    for(int i=1; i<n; i++)
        if(!chk[i])
        {
            memset(flag,0,sizeof(flag));
            flag[0] = true;
            block[nb] = i;
            rem += prim_heap(i,n-1); // 1 ~ n - 1
            for(int j=1; j<n; j++)
                if(flag[j])
                {
                    vec[nb].push_back(j);
                    chk[j] = true;
                }

            nb++;
        }

    for(int i=0; i<nb; i++)
    {
        int mn  = inf,index = -1;
        Edge* tmp;
        for(int j=0; j<vec[i].size(); j++)
            for(Edge* p=adj[0]; p; p=p->next)
                if(p->v == vec[i][j])
                    if(p->dis < mn)
                    {
                        mn = p->dis;
                        index = vec[i][j];
                        tmp = p;
                        continue;
                    }
        addedge(index,0,mn,true,tree);  // link v0 to block
        addedge(0,index,mn,true,tree);
        tmp->flag = false;                // deleting edge
        (((tmp-pool)^1) + pool)->flag = false;
        rem += mn;
        degree--;
    }
    while(degree > 0) // deleting edge
    {
        degree -- ;
        int mx = -inf;
        Edge *tmpAdd,*tmpDel;
        for(Edge* p=adj[0]; p; p=p->next)
        {
            if(p->flag)
            {
                memset(flag,0,sizeof(flag));
                dfs(0,p->v);
                int now = 0;
                memset(flag,0,sizeof(flag));
                while(pre[now] != 0)
                {
                    flag[now] = true;
                    now = pre[now];
                }
                flag[now] = true;
                calMinEdge(0,-inf);
                int delta =  minEdge->dis - p->dis ;
                if(delta > mx)
                {
                    mx = delta;
                    tmpAdd = p;
                    tmpDel = minEdge;
                }
            }
        }
        if(mx <= 0 )
            break;
        rem -= mx;
        addedge(tmpAdd->v,0,mx,true,tree);  // link new edge
        addedge(0,tmpAdd->v,mx,true,tree);
        tmpAdd->flag = false;              // delete old edge
        (((tmpAdd-pool)^1) + pool)->flag = false;
        tmpDel->flag = false;              // delete old edge
        (((tmpDel-pool)^1) + pool)->flag = false;
    }
    printf("Total miles driven: %d\n",rem);
    return 0;
}

解题报告转自:http://www.cnblogs.com/luyi0619/archive/2011/07/15/2107821.html


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 不考虑最后将结果排序的话,快排的时间复杂度是O(N) ,而堆排的是O(N*logK),这样比较看,快排快

  3. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }