竞赛图的得分序列（SRM 717 div 1 250）

SRM 717 DIV 1 中出了这样一道题：

竞赛图就是把一个无向完全图的边定向后得到的有向图，得分序列就是每个点的出度构成的序列。

给出一个合法的竞赛图出度序列，要求构造出原图（原题是求（u, v）有路径的点对数，似乎有不需要构造出原图的方法）。

当时我的做法是直接构造一个网络，跑最大流。

比赛后总觉得这个题有什么神奇的性质，于是搜了一下相关资料：

有一篇关于得分序列的论文：
http://www.sciencedirect.com/science/article/pii/0095895679900455?via%3Dihub

其中介绍了一个性质：

Landau Theorem: 竞赛图的出度序列为${s_i}$的充要条件是对于任意的子集X，$\sum\limits_{i \in X} s_i \ge \tbinom{|X|}{2}$

1.必要性很容易证明：如果${s_i}$是竞赛图的得分序列，对于任意一个子集X，它的得分之和一定大于等于它内部点之间的得分和。

2.充分性证明：大致思路是构造一个二分图然后利用Hall定理证明完美匹配。

　首先把边<i, j> (i < j) 看做左边的点。右边部分，对于每个$s_i$ 搞出$s_i$个点（这些点记为$i$类点）。

　对于左边的点<i, j> , 向右边所有的$i$类点和$j$类点各连一条边。显然一个完美匹配和一个原图对应。

根据Hall定理，有完美匹配的充要条件是对于左边任意的点集X, $|H(X)| \ge |X|$. $H(X)$是右边与$X$中的点有边相连的点的集合。

对于左边任意的点集$X$，设集合$Y$为$X$中的边的端点的集合。即$Y = \{ x | (x, t) \in X \ or\ (t, x) \in X \}$

根据所给的条件，我们有 $ |X| \leq \tbinom{|Y|}{2} \leq \sum\limits_{i \in Y} s_i = |H(X)|$, 所以存在完美匹配。定理得证。

接下来我们怎么用这个定理来构造原图呢？

当然可以构造出二分图然后跑最大匹配。

我自己又YY了一种贪心做法：

大致思想是不断给边定向，但是要让得分序列满足Landau Theorem。

先将所有点按$s_i$ 从小到大排序，考虑 $s_i$最小的那个点x，有$n - 1 - s_i$ 条边指向它，我们确定哪些点向它连边，让这些点的score -1. 显然贪心一下让score 最大的$n - 1 - s_i$个点向它连边最优。对于其它的点， x向它们连边就好。

AC代码：

 // BEGIN CUT HERE  

 // END CUT HERE

 #line 5 "ScoresSequence.cpp"

 #include <vector>

 #include <list>

 #include <map>

 #include <set>

 #include <deque>

 #include <stack>

 #include <bitset>

 #include <algorithm>

 #include <functional>

 #include <numeric>

 #include <utility>

 #include <sstream>

 #include <iostream>

 #include <iomanip>

 #include <cstdio>

 #include <cmath>

 #include <cstdlib>

 #include <ctime>

 #include <cstring>

 using namespace std;

 #define N 102

 const int INF = 1e9 + ;

 bool a[N][N];

 vector<pair<int, int> > lis, tmp;

 class ScoresSequence

 {

 public:

     int count(vector <int> s)

     {

         int n = s.size();

         memset(a, , sizeof(a));

         for (int i = ; i < n; ++i) a[i][i] = true;

         lis.clear();

         for (int i = ; i < n; ++i) lis.push_back(make_pair(s[i], i));

         for (int i = ; i < n - ; ++i)

         {

             sort(lis.begin(), lis.end());

             int c = n - i - lis[].first - ;

             for (int k = ; k <= c; ++k)

             {

                 lis[n - i - k].first--;

                 a[lis[n - i - k].second][lis[].second] = true;

             }

             for (int k = ; k < n - i - c; ++k)

                 a[lis[].second][lis[k].second] = true;

             tmp.clear();

             for (int j = ; j < lis.size(); ++j) tmp.push_back(lis[j]);

             lis = tmp;

         }

         int ans = ;

         for (int k = ; k < n; ++k)

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

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

                     a[i][j] |= a[i][k] & a[k][j];

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

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

                 ans += a[i][j];

         return ans;

     }

 // BEGIN CUT HERE

     public:

     void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0(); if ((Case == -) || (Case == )) test_case_1(); if ((Case == -) || (Case == )) test_case_2(); if ((Case == -) || (Case == )) test_case_3(); if ((Case == -) || (Case == )) test_case_4(); }

     private:

     template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }

     void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }

     void test_case_0() { int Arr0[] = {, , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, count(Arg0)); }

     void test_case_1() { int Arr0[] = {, , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, count(Arg0)); }

     void test_case_2() { int Arr0[] = {, , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, count(Arg0)); }

     void test_case_3() { int Arr0[] = {, , , , , , , , , }; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, count(Arg0)); }

     void test_case_4() { int Arr0[] = {,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, count(Arg0)); }

 // END CUT HERE

 };  

 // BEGIN CUT HERE

 int main()

 {

 ScoresSequence ___test;

 ___test.run_test(-);

 system("pause");

 }

 // END CUT HERE

实现方法比较暴力，大概是 O(n^2 logn)

巴特西

竞赛图的得分序列（SRM 717 div 1 250）

最新文章

热门文章

巴特西

竞赛图的得分序列 （SRM 717 div 1 250）

最新文章

热门文章

竞赛图的得分序列（SRM 717 div 1 250）