题解

58 条题解

  • 3
    @ 2017-05-17 12:52:27

    注: 这道题和 poj1182 食物链很像.
    AC 代码如下:

    #include <iostream>
    #include <cctype>
    using namespace std;
    
    const int maxn = 410;
    int father[maxn];
    
    int find(int x) {
        if (x == father[x])
            return x;
        else
            return father[x] = find(father[x]);
    }
    
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        father[x] = y;
    }
    
    int main() {
        ios::sync_with_stdio(false);
        int n, m, q;
        cin >> n >> m >> q;
        for (int i = 1; i <= 2 * n; i++)
            father[i] = i;
        while (m--) {
            string s;
            cin >> s;
            int num1 = s[1] - '0';
            if (isdigit(s[2])) num1 = num1 * 10 + s[2] - '0';
            if (isdigit(s[3])) num1 = num1 * 10 + s[3] - '0';
            char ch;
            cin >> ch;
            cin >> s;
            int num2 = s[1] - '0';
            if (isdigit(s[2])) num2 = num2 * 10 + s[2] - '0';
            if (isdigit(s[3])) num2 = num2 * 10 + s[3] - '0';
            if (ch == 'p') {
                if (find(num1) == find(num2 + n)) {
                    cout << "There must be something wrong..." << endl;
                    return 0;
                }
                unite(num1, num2);
                unite(num1 + n, num2 + n);
            } else {
                if (find(num1) == find(num2)) {
                    cout << "There must be something wrong..." << endl;
                    return 0;
                }
                unite(num1, num2 + n);
                unite(num1 + n, num2);
            }
        }
        int _count = 0;
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                if (find(i) == find(j) || find(i + n) == find(j + n))
                    _count++;
        cout << _count << endl;
        while (q--) {
            string s;
            cin >> s;
            int num1 = s[1] - '0';
            if (isdigit(s[2])) num1 = num1 * 10 + s[2] - '0';
            if (isdigit(s[3])) num1 = num1 * 10 + s[3] - '0';
            cin >> s;
            int num2 = s[1] - '0';
            if (isdigit(s[2])) num2 = num2 * 10 + s[2] - '0';
            if (isdigit(s[3])) num2 = num2 * 10 + s[3] - '0';
            if (find(num1) == find(num2) || find(num1 + n) == find(num2 + n))
                cout << "Parallel." << endl;
            else if (find(num1) == find(num2 + n) || find(num1 + n) == find(num2))
                cout << "Vertical." << endl;
            else
                cout << "No idea." << endl;
        }
        return 0;
    }
    
  • 1
    @ 2020-05-09 15:38:20
    #include<bits/stdc++.h>
    using namespace std;
    const int N = 200, M = 401;
    int fa[M], sum[M], ans;
    bool v[N + 1];
    int find(int x) {
            return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    void u(int x, int y) {
            sum[fa[x]] += sum[find(y)];
            fa[find(y)] = fa[x];
    }
    int main() {
            ios::sync_with_stdio(false);
            cin.tie(0);
            int n, m, p;
            cin >> n >> m >> p;
            for (int i = 1; i <= N; i++)
                    sum[i] = 1;
            for (int i = 1; i <= M; i++)
                    fa[i] = i;
            for (int i = 1; i <= m; i++) {
                    int x, y;
                    char a, c;
                    cin >> a >> x >> c >> a >> y;
                    if (c == 'p')
                            u(x, y), u(x + N, y + N);
                    else
                            u(x + N, y), u(x, y + N);
            }
            for (int i = 1; i <= n; i++) {
                    if (fa[i] == fa[i + N]) {
                            cout << "There must be something wrong...";
                            return 0;
                    }
                    if (!v[find(i)]) {
                            ans += sum[fa[i]] * (sum[fa[i]] - 1) / 2;
                            v[fa[i]] = 1;
                    }
            }
            cout << ans << '\n';
            for (int i = 1; i <= p; i++) {
                    int x, y;
                    char a;
                    cin >> a >> x >> a >> y;
                    if (fa[x] == fa[y])
                            cout << "Parallel." << '\n';
                    else if (fa[x] == fa[y + N])
                            cout << "Vertical." << '\n';
                    else
                            cout << "No idea." << '\n';
            }
            return 0;
    }
    
  • 0
    @ 2017-09-13 11:36:07

    #include<iostream>
    #include<cstring>
    using namespace std;

    int n, m, q;
    int g[201][201];
    bool visited[201][201];
    int s, ans = 0;
    void dfs(int ahead, int i) {
    int j;
    if (g[s][i] == 0 && ahead != i && ahead != s && i != s) {
    if ((g[s][ahead] == 1 && g[ahead][i] == 1) || (g[s][ahead] == 2 && g[ahead][i] == 2)) {
    g[s][i] = 1;
    g[i][s] = 1;
    }
    else {
    g[s][i] = 2; g[i][s] = 2;
    }
    }
    for (j = 1; j <= n; j++) {
    if (g[i][j] > 0 && !visited[i][j]) {
    visited[i][j] = true;
    visited[j][i] = true;
    dfs(i, j);
    }
    }
    }
    int main() {
    memset(g, 0, sizeof(g));
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
    char c, state;
    int l1, l2;
    cin >> c >> l1 >> state >> c >> l2;
    if (state == 'p') {
    if (g[l1][l2] != 0) {
    cout << "There must be something wrong..." << endl;
    return 0;
    }
    g[l1][l2] = 1; g[l2][l1] = 1;
    }
    else {
    g[l1][l2] = 2;
    g[l2][l1] = 2;
    }
    }
    for (int i = 1; i <= n; i++) {
    memset(visited, false, sizeof(visited));
    s = i;
    dfs(s, s);
    }

    for (int i = 1; i < n; i++) {
    for (int j = i + 1; j <= n; j++) {
    if (g[i][j] == 1) ans++;
    }
    }

    cout << ans << endl;
    char c;
    int l1, l2;
    for (int i = 0; i < q; i++) {
    cin >> c >> l1 >> c >> l2;
    if (g[l1][l2] == 0) cout << "No idea." << endl;
    else if (g[l1][l2] == 1) cout << "Parallel." << endl;
    else cout << "Vertical." << endl;
    }
    return 0;
    }

  • 0
    @ 2017-04-10 15:12:37

    ???
    BF题解在这。。。
    题解

    • @ 2017-05-17 12:47:47

      什么乱七八糟的?

    • @ 2017-07-03 12:05:52

      @larryzhong: Bellman-ford 最短路算法

  • 0
    @ 2016-07-22 10:12:04

    良心题解
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    using namespace std;
    int n,m,q,f[410],ans(0);
    int used[210];
    bool p(0);
    char s;
    struct p
    {
    int x,y,z;
    }e[1005];
    int find(int x)
    {
    if(f[x]==x)return x;
    return find(f[x]);
    }
    void UN(int x,int y)
    {
    int a=find(x);
    int b=find(y);
    f[a]=b;
    }
    int main()
    {
    scanf("%d %d %d\n",&n,&m,&q);
    for(int i=1;i<=2*n;i++)
    f[i]=i;
    for(int i=1;i<=m;i++)
    {
    getchar();
    scanf("%d",&e[i].x);
    getchar();
    s=getchar();
    getchar();
    getchar();
    scanf("%d",&e[i].y);
    if(s=='p')
    {
    if(find(e[i].x)!=find(e[i].y+n)&&find(e[i].y)!=find(e[i].x+n))
    {
    UN(e[i].x,e[i].y);
    UN(e[i].x+n,e[i].y+n);
    }
    else
    {
    printf("There must be something wrong...\n");
    p=1;
    break;
    }
    }
    else
    if(s=='v')
    {
    if(find(e[i].x)!=find(e[i].y)&&find(e[i].x+n)!=find(e[i].y+n))
    {
    UN(e[i].x,e[i].y+n);
    UN(e[i].y,e[i].x+n);
    }
    else
    {
    printf("There must be something wrong...\n");
    p=1;
    break;
    }
    }
    getchar();
    }
    if(p==0)
    {
    for(int i=1;i<=n-1;i++)
    {
    for(int j=i+1;j<=n;j++)
    {
    if(find(i)==find(j)&&used[j]==0)
    {
    used[j]=1;
    // printf("%d %d\n",i,j);
    ans++;
    }
    if(find(i)==find(j+n))
    {
    for(int o=j+1;o<=n;o++)
    {
    if(find(o)==find(j+n)&&used[o]==0)
    {
    used[o]=1;
    // printf("%d %d %d\n",i,j,o);
    ans++;
    }
    }
    }
    }
    memset(used,0,sizeof(used));
    }
    }
    //printf("-----------------\n");
    if(p==0)
    printf("%d\n",ans);
    if(p==0)
    {
    for(int i=1;i<=q;i++)
    {
    int x,y;
    getchar();
    scanf("%d",&x);
    getchar();
    getchar();
    scanf("%d",&y);
    getchar();
    if(find(x)==find(y))
    printf("Parallel.\n");
    else
    if(find(x)==find(y+n))
    printf("Vertical.\n");
    else
    printf("No idea.\n");
    }
    }
    return 0;
    }

  • 0
    @ 2009-11-14 21:08:11

    回:voyagec2

    原来是L1,L2,不是11,12 ...

    嗯?什么情况..应该小写才对..

  • -1
    @ 2015-07-01 10:48:30

    P1697平面几何
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1697 平面几何
    递交时间 2015-07-01 10:44:11
    代码语言 C++
    评测机 VijosEx
    消耗时间 46 ms
    消耗内存 284 KiB
    评测时间 2015-07-01 10:44:13

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 280 KiB, score = 20

    测试数据 #1: Accepted, time = 0 ms, mem = 280 KiB, score = 20

    测试数据 #2: Accepted, time = 0 ms, mem = 284 KiB, score = 20

    测试数据 #3: Accepted, time = 15 ms, mem = 280 KiB, score = 20

    测试数据 #4: Accepted, time = 31 ms, mem = 284 KiB, score = 20

    Accepted, time = 46 ms, mem = 284 KiB, score = 100

    代码

    #include <iostream>
    #include <stdio.h>

    using namespace std;

    int n , m , q;
    int i , j , k;
    char s[1000];
    int x , y;
    int ans;
    int pre[ 200 + 10 ];
    int cond[ 200 + 10 ];
    int e;
    char st;

    int find( int x )
    {
    if( x == pre[x] )
    return x;
    return find( pre[x] );
    }

    int sta( int x )
    {
    int st = 1;
    while( x != pre[x] )
    {
    st *= cond[x];
    x = pre[x];
    }
    st *= cond[x];
    return st;
    }

    void merge( int x , int y, int st )
    {
    int t = find( x );
    cond[ t ] = sta( x ) * st;
    pre[ t ] = y;
    return;
    }

    int main()
    {
    scanf( "%d %d %d" , &n , &m , &q );
    for( i = 1 ; i <= n ; i++ )
    {
    pre[i] = i;
    cond[i] = 1;
    }
    getchar();
    for( i = 0 ; i < m ; i++ )
    {
    x = y = 0;

    cin >> s;
    for( k = 1 ; s[k] != 0 && s[k] != '\0' ; k++ )
    {
    x *= 10;
    x += s[k] - '0';
    }

    cin >> s;
    st = s[0];
    cin >> s;
    for( k = 1 ; s[k] != 0 && s[k] != '\0' ; k++ )
    {
    y *= 10;
    y += s[k] - '0';
    }
    if( st == 'p' )
    {
    if( find( x ) != find( y ) )
    merge( x , y , 1 );
    else if( sta( x ) == sta( y ) )
    ;
    else
    {
    printf( "There must be something wrong...\n" );
    return 0;
    }
    }
    else
    {
    if( find( x ) != find( y ) )
    merge( x , y , -1 );
    else if( sta( x ) == -sta( y ) )
    ;
    else
    {
    printf( "There must be something wrong...\n" );
    return 0;
    }
    }
    }
    for( i = 1 ; i <= n ; i++ )
    for( j = i + 1 ; j <= n ; j++ )
    if( find( i ) == find( j ) && sta( i ) == sta( j ) )
    ans++;
    cout << ans << endl;
    for( i = 0 ; i < q ; i++ )
    {
    scanf( "%s" , s );
    x = y = 0;
    for( k = 1 ; s[k] != 0 && s[k] != '\0' ; k++ )
    {
    x *= 10;
    x += s[k] - '0';
    }
    scanf( "%s" , s );
    for( k = 1 ; s[k] != 0 && s[k] != '\0' ; k++ )
    {
    y *= 10;
    y += s[k] - '0';
    }
    if( find( x ) == find( y ) )
    {
    e = sta( x ) * sta( y );
    if( e > 0 )
    printf( "Parallel.\n" );
    else
    printf( "Vertical.\n" );
    }
    else
    printf( "No idea.\n" );
    }
    //system( "pause" );
    return 0;
    }

  • -1
    @ 2015-03-01 16:44:47

    评测结果
    编译成功

    foo.cpp: In function 'int main()':
    foo.cpp:9:10: warning: unused variable 'l2' [-Wunused-variable]
    char l1,l2,l3,l4,ch;
    ^
    测试数据 #0: Accepted, time = 0 ms, mem = 684 KiB, score = 20
    测试数据 #1: Accepted, time = 0 ms, mem = 688 KiB, score = 20
    测试数据 #2: Accepted, time = 0 ms, mem = 688 KiB, score = 20
    测试数据 #3: Accepted, time = 0 ms, mem = 688 KiB, score = 20
    测试数据 #4: Accepted, time = 62 ms, mem = 684 KiB, score = 20
    Accepted, time = 62 ms, mem = 688 KiB, score = 100
    代码
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int a[210][210];
    int n,m,t;
    int main()
    {
    cin>>n>>m>>t;
    char l1,l2,l3,l4,ch;
    int x,y,num;
    for(int i=1;i<=n;i++)
    a[i][i]=1;
    for(int i=1;i<=m;i++)
    {
    cin>>l1>>x>>ch>>l4>>y;
    num=a[x][y];
    if(ch=='p')
    {
    a[x][y]=1;
    a[y][x]=1;
    }
    if(ch=='v')
    {
    a[x][y]=-1;
    a[y][x]=-1;
    }
    if(num+a[x][y]==0)
    {
    cout<<"There must be something wrong..."<<endl;
    return 0;
    }
    }
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
    num=a[i][j];
    if((a[i][k]!=0)&&(a[j][k]!=0))
    a[i][j]=a[i][k]*a[j][k];
    a[j][i]=a[i][j];
    if((num!=0)&&(a[i][j]!=num))
    {
    cout<<"There must be something wrong..."<<endl;
    return 0;
    }
    }
    num=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if((a[i][j]==1)&&(i!=j)) num++;
    cout<<num/2<<endl;
    for(int i=1;i<=t;i++)
    {
    cin>>l1>>x>>l3>>y;
    if(a[x][y]==-1) cout<<"Vertical."<<endl;
    if(a[x][y]==1) cout<<"Parallel."<<endl;
    if(a[x][y]==0) cout<<"No idea."<<endl;
    }
    return 0;
    }

  • -1
    @ 2014-03-09 22:53:49

    测试数据 #0: Accepted, time = 0 ms, mem = 892 KiB, score = 20
    测试数据 #1: Accepted, time = 0 ms, mem = 888 KiB, score = 20
    测试数据 #2: Accepted, time = 0 ms, mem = 892 KiB, score = 20
    测试数据 #3: Accepted, time = 0 ms, mem = 888 KiB, score = 20
    测试数据 #4: Accepted, time = 0 ms, mem = 888 KiB, score = 20
    Accepted, time = 0 ms, mem = 892 KiB, score = 100

  • -1
    @ 2014-03-09 22:53:11

    秒杀。
    program p1697;
    var a,b,c,d:array[0..10000] of longint;
    n,m,p,sum:longint;
    //
    procedure init;
    var i:longint;
    begin
    readln(n,m,p);
    end;
    //
    function fa(p:longint):longint;
    var p1,p2,p3,p4,p5:longint;
    begin
    p1:=p;p2:=p;p3:=0;
    while p1<>a[p1] do
    begin
    p3:=p3+b[p1];p1:=a[p1];
    end;
    while p2<>p1 do
    begin
    p4:=a[p2];a[p2]:=p1;p5:=b[p2];b[p2]:=p3;
    p3:=p3-p5;p2:=p4;
    end;
    exit(p1);
    end;
    //
    procedure main;
    var i,p1,p2,p3,h1,h2:longint;
    c:char;
    begin
    for i:=1 to n do a[i]:=i;
    for i:=1 to m do
    begin
    read(c);read(p1);read(c);read(c);
    if c='p' then p3:=0
    else p3:=1;
    read(c);read(c);readln(p2);
    h1:=fa(p1);h2:=fa(p2);
    if h1=h2 then
    if (abs((b[p1] mod 2)-(b[p2] mod 2)) mod 2)<>p3 then
    begin
    write('There must be something wrong...');
    close(output);halt;
    end;
    if h1<>h2 then
    begin
    a[h1]:=h2;b[h1]:=((b[p1]+p3-b[p2]) mod 2+2) mod 2;
    end;
    end;
    end;
    //
    procedure print;
    var i,h,h1,h2,p1,p2:longint;
    cc:char;
    begin
    for i:=1 to n do
    begin
    h:=fa(i);
    if b[i] mod 2=0 then inc(c[h])
    else inc(d[h]);
    end;
    for i:=1 to n do sum:=sum+((c[i]*(c[i]-1)) div 2)+((d[i]*(d[i]-1)) div 2);
    writeln(sum);
    for i:=1 to p do
    begin
    read(cc);read(p1);read(cc);read(cc);readln(p2);
    h1:=fa(p1);h2:=fa(p2);
    if h1=h2 then
    begin
    if (abs(b[p1]-b[p2]) mod 2+2) mod 2=1 then writeln('Vertical.')
    else writeln('Parallel.');
    end
    else writeln('No idea.');
    end;
    end;
    //
    begin
    init;
    main;
    print;
    end.

  • -1
    @ 2010-07-17 19:19:43

    var x,y,n,m,i,j,q,s,k:longint;

    c,cc:char;

    a:array [0..200,0..200] of longint;

    begin

    assign(input,'geometry.in');reset(input);

    assign(output,'geometry.out');rewrite(output);

    readln(n,m,q);

    for i:=1 to m do

    begin

    readln(c,x,c,cc,c,c,y);

    if a[x,y]>0 then

    begin

    writeln('There must be something wrong...');

    close(input);close(output);

    halt;

    end;

    if cc='p' then a[x,y]:=1 else a[x,y]:=2;

    a[y,x]:=a[x,y];

    end;

    for k:=1 to n do

    for i:=1 to n do

    for j:=1 to n do

    if (ij) and (ik) and (kj) and (a=0)

    and (a>0) and (a[k,j]>0) then

    begin

    if a=a[k,j] then a:=1

    else a:=2;

    a[j,i]:=a;

    end;

    for i:=1 to n-1 do

    for j:=i+1 to n do

    if a=1 then inc(s);

    writeln(s);

    for i:=1 to q do

    begin

    readln(c,x,c,c,y);

    if a[x,y]=1 then writeln('Parallel.');

    if a[x,y]=2 then writeln('Vertical.');

    if a[x,y]=0 then writeln('No idea.');

    end;

    close(input);close(output);

    end.

  • -1
    @ 2010-03-03 13:10:12

    没人在哇 都是09年11月的留言

  • -1
    @ 2009-11-11 19:54:21

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    写了并查集,效率很高。。

    其实这一道题目是食物链的弱化版,只要用加权的并查集就能秒杀。。。

    还有就是细节处理要注意,特别是读入数据的部分,有点不爽!!!

    幸好一次AC

  • -1
    @ 2009-11-11 19:49:56

    感慨啊!这题终于过了啊!

    先用并查集,调了n次,信心丧失。

    后来改变算法,用floyd的传递闭包,终于过了!

    好开心!!!

  • -1
    @ 2009-11-10 13:44:54

    Flag Unaccepted

    题号 P1697

    类型(?) 其他

    通过 250人

    提交 682

    通过率 37%

  • -1
    @ 2009-11-10 09:52:47

    明明知道可以floyed(代碼60+),結果無聊寫了一個并查集(代碼100+),

    結果調了N久,以後還是要KISS啊!

  • -1
    @ 2009-11-09 20:47:15

    Floyed 真正有用的部分…………

    说实话预处理比较烦,直接给不就行了,还得在前面加个字母…………

    bool long_link(int k)

    {int i,j;

    int tmp;

    for(i=1;i

  • -1
    @ 2009-11-09 14:44:34

    '哎呀...测试数据都是很善意的...我们没有刻意要害大家...'

    那么就不应该有第二组数据!!!

    感谢HeavenSea,不然还真想不到这么贱的数据

  • -1
    @ 2009-11-09 11:04:17

    Floyd's Algorithm

    或者类似于

    PKU ACM 1182 食物链 的算法

  • -1
    @ 2009-11-09 10:43:31

    谁有第四组数据,这组我总错

信息

ID
1697
难度
7
分类
数据结构 | 并查集 点击显示
标签
递交数
1961
已通过
450
通过率
23%
被复制
1
上传者