Instability（typedef pair<LL,int> P;）

灰太狼 2022-06-09 01:06 156阅读 0赞

# Instability #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)  
Total Submission(s): 471    Accepted Submission(s): 176**

Problem Description

Long long ago, there was a prosperous kingdom which consisted of n cities and every two cites were connected by an undirected road.  
  
However, one day a big monster attacked the kingdom and some roads were destroyed. In order to evaluate the influence brought by the catastrophe, the king wanted to know the instability of his kingdom. Instability is defined as the number of the unstable subset of \{1, 2,  ⋯![Image 1][],n\}.  
  
A set S is unstable if and only if there exists a set A such that  A⊆S(|A|≥3![Image 1][]) and A is a **clique** or an **independent set**, namely that cites in A are pairwise connected **directly** or they are pairwise disconnected.  
  
Archaeologist has already restored themroads that were not destroyed by the monster. And they want you to figure out the instability.  
  
Since the answer may be tremendously huge, you are only required to write a program that prints the answer modulo 1000000007.

Input

The first line contains only one integer T, which indicates the number of test cases.  
  
For each test case, the first line contains two integers n (  3≤n≤50![Image 1][]) and m (  1≤m≤n(n−1)/2![Image 1][]), indicating the number of cities and the number of roads.  
  
Then the following are m lines, each of which contains two integers x and y, indicating there is a road between the city x and the city y.  
  
It is guarenteed that there does not exist a road connecting the same city and there does not exist two same roads.

Output

For each test case, print a line “Case \#x: y”, where x is the case number (starting from 1) and y is an integer indicating the instability modulo 1000000007.

Sample Input

2
    4 3
    1 2
    2 3
    1 3
    3 0

Sample Output

Case #1: 2
    Case #2: 1
    
    
       
        Hint • In the first example, {1,2,3} and {1,2,3,4} , containing the subset {1,2,3} which is connected directly, are considered unstable. • In the second example, {1,2,3} is considered unstable because they are not pairwise connected directly. 
       
        #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include<queue>
    using namespace std ;
    typedef __int64 LL;
    typedef pair<LL,int> P;
    const int mod = 1e9+7;
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            priority_queue<P> sk;
            priority_queue<int,vector<int>,greater<int> >b;
            LL ans=0;
            for(int i=1; i<=n; i++)
            {
                LL x;
                scanf("%lld",&x);
                sk.push(P(x-i,i));
            }
    //        while(!sk.empty())
    //        {
    //            printf("%lld %d\n",sk.top().first,sk.top().second);
    //            sk.pop();
    //        }
            for(int i=1; i<=n; i++)
            {
                int x;
                scanf("%lld",&x);
                b.push(x);
            }
            for(int ti=n+1; ti<=2*n; ti++)
            {
                int i=b.top();
                b.pop();
                while(sk.top().second<i)
                    sk.pop();
                P p=sk.top();
                sk.push(P(p.first-ti,ti));
                ans=(ans+p.first)%mod;
                //printf("%lld %lld\n",ans,p.first);
            }
            printf("%lld\n",ans);
        }
        return 0;
    }
    /*
    给出数列 A 和 B ，我们可以从 B 数列中取出一个编号来查找 A
    数列中该编号及以后的位置中 Ai−i 的最大值并将其加入末尾，
    求 An+1..A2n 的和。
    */

[Image 1]: