糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

POJ 1570 Exchange Rates 并查集

并查集加上分数运算就可以了。
两种物品之间的兑换比率可以用分数来表示,两种物品之间是否存在联系用并查集来表示。

#include <stdio.h>
#include 
<string.h>

typedef 
struct {
    
int a, b;
} frac ;

#define MAX_ITEM 64

char item[MAX_ITEM][32];
int item_cnt;

struct {
    frac f;
    
int p;
set[MAX_ITEM];

int gcd(int a, int b)
{
    
int t;

    
if (a > b) {
        a 
^= b;
        b 
^= a;
        a 
^= b;
    }

    
while (a) {
        t 
= a;
        a 
= b % a;
        b 
= t;
    }

    
return b;
}

frac init(
int a, int b)
{
    frac r;
    
int g = gcd(a, b);

    r.a 
= a / g;
    r.b 
= b / g;

    
return r;
}

frac mul(frac a, frac b)
{
    
return init(a.a * b.a, a.b * b.b);
}

frac div(frac a, frac b)
{
    
return init(a.a * b.b, a.b * b.a);
}

int find(int i)
{
    
int p;

    
if (set[i].p == i)
        
return i;

    p 
= find(set[i].p);
    
set[i].f = mul(set[set[i].p].f, set[i].f);
    
set[i].p = p;

    
return p;
}

int insert(char *s)
{
    
int i;

    
for (i = 0; i < item_cnt; i++)
        
if (!strcmp(s, item[i]))
            
return i;
    strcpy(item[item_cnt], s);
    
return item_cnt++;
}

int main()
{
    
char op[16], sa[32], sb[32];
    
int a, b, ia, ib, i, p;
    frac f;

    
for (i = 0; i < MAX_ITEM; i++) {
        
set[i].p = i;
        
set[i].f = init(11);
    }

    
while (scanf("%s", op), op[0!= '.') {
        
if (op[0== '!') {
            scanf(
"%d%s%*s%d%s"&a, sa, &b, sb);
            ia 
= insert(sa);
            ib 
= insert(sb);
            find(ia);
            p 
= set[ia].p;
            
set[p].p = ib;
            
set[p].f = div(init(b, a), set[ia].f);
        } 
else {
            scanf(
"%s%*s%s", sa, sb);
            ia 
= insert(sa);
            ib 
= insert(sb);
            find(ia);
            find(ib);
            
if (set[ia].p == set[ib].p) {
                f 
= div(set[ia].f, set[ib].f);
                printf(
"%d %s = %d %s\n", f.b, item[ia], f.a, item[ib]);
            } 
else 
                printf(
"? %s = ? %s\n", item[ia], item[ib]);
        }
    }

    
return 0;
}


posted on 2010-07-22 11:59 糯米 阅读(369) 评论(0)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理