topcoder srm 692 div1 -23

1、给定一个带权有向图。选出一些边满足使得任意两点可相互到达的前提下使得选出的边的权值的最大最小差值最小。

思路：二分答案，然后枚举权值的范围判断是否可行。

#include <stdio.h>

#include <string>

#include <stack>

#include <vector>

#include <string.h>

#include <algorithm>

using namespace std;

vector<int> g1[55];

vector<int> g2[55];

class HardProof

{

    int n;

    int G[55][55];

    int a[55*55],aNum;

    void dfs(int u,int f[],vector<int> g[55])

    {

        if(f[u]) return;

        f[u]=1;

        for(int i=0;i<(int)g[u].size();++i)

        {

            int v=g[u][i];

            dfs(v,f,g);

        }

    }

    int check(int M)

    {

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

        {

            const int S=a[i];

            for(int i=0;i<n;++i) g1[i].clear(),g2[i].clear();

            for(int i=0;i<n;++i) {

                for(int j=0;j<n;++j) {

                    if(i!=j&&S<=G[i][j]&&G[i][j]<=S+M) {

                        g1[i].push_back(j);

                        g2[j].push_back(i);

                    }

                }

            }

            int f1[55],f2[55];

            memset(f1,0,sizeof(f1));

            memset(f2,0,sizeof(f2));

            dfs(0,f1,g1);

            dfs(0,f2,g2);

            for(int i=0;i<n;++i) {

                if(!f1[i]||!f2[i]) break;

                if(i==n-1) return 1;

            }

        }

        return 0;

    }

public:

	int minimumCost(vector<int> D)

	{

	    n=1;

	    while(n*n!=(int)D.size()) ++n;

	    if(1==n) return 0;

	    int low=150000,high=0;

	    aNum=0;

	    for(int i=0;i<n;++i) {

            for(int j=0;j<n;++j) if(i!=j) {

                int p=D[i*n+j];

                if(p<low) low=p;

                if(p>high) high=p;

                G[i][j]=p;

                a[++aNum]=p;

            }

	    }

        sort(a+1,a+aNum+1);

        aNum=unique(a+1,a+aNum+1)-(a+1);

        high=high-low;

        low=0;

        int ans=high;

        while(low<=high)

        {

            int M=(low+high)>>1;

            if(check(M)) ans=min(ans,M),high=M-1;

            else low=M+1;

        }

        return ans;

	}

};