Morris' Blog

2011-10-02 09:33:23Morris

a254. 畢氏‧三角‧製造

留言 0 收藏 0 推薦 0

內容：

        一個「最約畢氏三角」( primitive Pythagorean triangle) 的定義是指一個三角形滿足：三邊長a, b, c都是正整數且 a2 + b2 = c2 ，以及比較短的兩邊長a, b的最大公因數為1。
老國王想要教導小王子學習畢氏三角的精隨與奧妙，於是給了小王子一些不同長度的木棍，要他利用這些木棍製造出許多「最約畢氏三角」。因為製造材料的關係，
這些木棍僅被拿來用在比較短的兩個邊上，而且由於使用工具切木棍太危險了，因此木棍必須被整根使用。比方說妳有兩根長度分別是3和4的木棍，就可以做出一個三邊邊長分別是3, 4, 5的畢氏三角。
        現在小王子拿到了很多很多木棍，請你計算這些木棍最多可以製作多少個「最約畢氏三角」，注意每根木棍至多只能被用一次。

輸入說明：

        每個測資檔內含有多組測資。每組測資第一列有一個正整數N(1<=N<=200)，接下來包含了N個正整數代表木棍長度，所有數字都介於1到999999之間。

輸出說明：

        對於每一組測試資料請輸出能拿來湊出的最多最約畢氏三角的數量。

範例輸入：

9
3 4 4 3 11 5 12 9 4
4
20 21 3021 220
5
28 195 1035 21412 37995

範例輸出：

3
2
2

提示：

出處：

 
  成功高中校內賽初賽 第四題
  
    (管理：david942j)

作法 : 匹配

maxflow + SPFA

/**********************************************************************************/
/* Problem: a254 "畢氏‧三角‧製造" from 成功高中校內賽初賽第四題*/
/* Language: C (1431 Bytes)                                                      */
/* Result: AC(211ms, 879KB) judge by this@ZeroJudge                              */
/* Author: morris1028 at 2011-10-02 08:57:25                                     */
/**********************************************************************************/

#include<stdio.h>
#include<string.h>
#include<math.h>
#define oo 10000
int Map[402][402];
int max_flow(int st, int ed, int n) {
    int maxflow = 0, tn, tw, a, b;
    int pre[n+1], V[n+1];
    char Used[n+1];
    int Q[100001], Qt;
    while(1) {
        memset(Used, 0, sizeof(Used));
        memset(V, 0, sizeof(V));
        V[st] = oo;
        Qt = 0, Q[0] = st, pre[st] = st;
        for(a = 0; a <= Qt; a++) {
            tn = Q[a], Used[tn] = 0;
            for(b = 1; b <= n; b++) {
                tw = (V[tn] < Map[tn][b]) ? V[tn] : Map[tn][b];
                if(tw > V[b]) {
                    V[b] = tw, pre[b] = tn;
                    if(Used[b] == 0)
                        Q[++Qt] = b, Used[b] = 1;
                }
            }
        }
        if(V[ed] == 0) break;
        maxflow += V[ed];
        for(a = ed; a != st; a = pre[a]) {
            Map[pre[a]][a] -= V[ed], Map[a][pre[a]] += V[ed];
        }
    }
    return maxflow;
}
long long GCD(long long x, long long y) {
    int t;
    while(x%y) {
        t = x, x = y, y = t%y;
    }
    return y;
}
main() {
    int n, i, j;
    long long tmp1, tmp2, A[201];
    while(scanf("%d", &n) == 1) {
        memset(Map, 0, sizeof(Map));
        int st = 0, ed = 2*n+1;
        for(i = 1; i <= n; i++)
            scanf("%lld", &A[i]);
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++) {
                tmp1 = A[i]*A[i] + A[j]*A[j];
                tmp2 = (int)sqrt(tmp1);
                if(GCD(A[i], A[j]) == 1 && tmp1 == tmp2*tmp2)
                    Map[i][n+j] = 1;
            }
        for(i = 1; i <= n; i++)        Map[st][i] = 1, Map[i+n][ed] = 1;
        printf("%d\n", max_flow(st, ed, 2*n+1)/2);
    }
    return 0;
}

作法 : 匈牙利演算法

/**********************************************************************************/
/* Problem: a254 "畢氏‧三角‧製造" from 成功高中校內賽初賽第四題*/
/* Language: C (1081 Bytes)                                                      */
/* Result: AC(35ms, 365KB) judge by this@ZeroJudge                               */
/* Author: morris1028 at 2011-10-02 09:06:43                                     */
/**********************************************************************************/

#include<stdio.h>
#include<math.h>
#include<string.h>
int map[201][201], Mt[201];
char used[201];
int mx[201], my[201];
int DFS(int now) {
    int a, i;
    for(a = 0; a < Mt[now]; a++) {
        i = map[now][a];
        if(!used[i]) {
            used[i] = 1;
            if(my[i] == 0 || DFS(my[i])) {
                mx[now] = i, my[i] = now;
                return 1;
            }
        }
    }
    return 0;
}
long long GCD(long long x, long long y) {
    int t;
    while(x%y) {
        t = x, x = y, y = t%y;
    }
    return y;
}
main() {
    int n, i, j;
    long long tmp1, tmp2, A[201];
    while(scanf("%d", &n) == 1) {
        memset(Mt, 0, sizeof(Mt));
        for(i = 1; i <= n; i++)
            scanf("%lld", &A[i]);
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++) {
                tmp1 = A[i]*A[i] + A[j]*A[j];
                tmp2 = (int)sqrt(tmp1);
                if(GCD(A[i], A[j]) == 1 && tmp1 == tmp2*tmp2)
                    map[i][Mt[i]++] = j;
            }
        memset(mx, 0, sizeof(mx));
        memset(my, 0, sizeof(my));
        int Ans = 0;
        for(i = 1; i <= n; i++)
            if(!mx[i]) {
                memset(used, 0, sizeof(used));
                if(DFS(i))
                    Ans++;
            }
        printf("%d\n", Ans/2);
    }
    return 0;
}

上一篇：a253. 王老先生的磨菇田

下一篇：a245. 王老師愛兩條線

Morris' Blog

a254. 畢氏‧三角‧製造

你可能感興趣的文章

四月南風-八仙賀喜好運翻倍，人氣過年禮盒推薦!

攻罵小呂榮

第五關：第134天

生活綜合｜【咖啡硬in】極限萃取瑪卡錠，滿滿的咖啡香味讓我身體維持良好狀態

Raimundo Arrais do Rosário