Walls POJ 1161

大牛さんのブログを参考にしました 
http://blog.csdn.net/wangjian8006/article/details/7958838
テーマ:
n個の点を与えて、これらの点の中でいくつかの点はクラブの点で、そしてm個の領域は点によって囲まれた入力の第1行はn個の点の第2行はm個の領域の第3行はクラブを代表してL個の第4行はL個の数があって、それぞれどの点がクラブの次の2*m行で、m個の領域を代表して、各領域は2行で表して、第1の行為の領域はT個の点で囲まれて、2行目のT個の数はどの点がこの領域に囲まれているかを表し、これらの点は反時計回りにこの領域に囲まれており、隣接する2点は1つの辺の最後の点と1つの点も1つの辺であり、このように閉じた領域である.
ここで、図の中で1つの領域を見つけて、すべてのクラブポイントがこの領域に通過するエッジの和が最も少なく、最も少ないエッジ数の和を出力します.
テーマ構想:
2つの領域に共通のエッジがある場合、2つの領域の距離は1であり、Floydはすべての領域の距離を求める.
残りの暴力解决でOK
 

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <queue>

#include <cmath>

#include <cstring>

using namespace std;

#define INF 0xfffffff

#define maxn 260



struct Area

{

    int num;

    int Point[maxn];

    bool vis[maxn];

} P[maxn];



int G[maxn][maxn], Member[maxn];

int n, m, a;//n   m    a         



void Floyd();

bool Adj(Area A, Area B);

int Slove();

int CountPoint(int k);



int main()

{

    cin >> m >> n >> a;



    for(int i=0; i<a; i++)

        cin >> Member[i];



    for(int i=0; i<m; i++)

    {

        cin >> P[i].num;



        for(int j=0; j<P[i].num; j++)

        {

            cin >> P[i].Point[j];

            P[i].vis[ P[i].Point[j] ] = true;

        }



        P[i].Point[P[i].num] = P[i].Point[0];

    }



    for(int i=0; i<m; i++)

    {

        for(int j=0; j<i; j++)

        {

            G[i][j] = INF;

            if( Adj(P[i], P[j]) )

                G[i][j] = 1;



            G[j][i] = G[i][j];

        }

        G[i][i] = 0;

    }



    Floyd();



    int ans = Slove();



    cout << ans << endl;



    return 0;

}

void Floyd()

{

    for(int k=0; k<m; k++)

    {

        for(int i=0; i<m; i++)

        {

            for(int j=0; j<m; j++)

            {

                if(G[i][j] > G[i][k] + G[k][j] )

                {

                    G[i][j] = G[i][k] + G[k][j];

                }

            }

        }

    }

}



bool Adj(Area A, Area B)

{

    for(int i=0; i< A.num; i++)

    {

        for(int j=0; j<B.num; j++)

        {

            if( (A.Point[i] == B.Point[j] && A.Point[i+1] == B.Point[j+1]) ||

                    (A.Point[i] == B.Point[j + 1] && A.Point[i+1] == B.Point[j]) )

                return true;

        }

    }

    return false;

}



int Slove()

{

    int index = 0, b[maxn];

    for(int i=0; i<m; i++)

    {

        b[i] = CountPoint(i);

    }



    for(int i=1; i<m; i++)

    {

        if(b[i] < b[index])

            index = i;

    }

    return b[index];

}



int CountPoint(int k)//             k         

{

    int sum = 0;



    for(int i=0; i<a; i++)

    {

        int Min = INF;

        for(int j=0; j<m; j++)

        {

            if( P[j].vis[ Member[i] ] && Min > G[j][k] )

            {

                Min = G[j][k];

            }

        }

        sum += Min;

    }

    return sum;

}