Contest 2

　　A：辣鸡题。搜索怎么这么难啊。不会啊。

　　B：裸的高斯消元，看起来可以优化到n²。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
#define N 210
int n,m;
double a[N][N],p;
void gauss()
{
    for (int i=0;i<n+m+1;i++)
    {
        int mx=i;
        for (int j=i+1;j<=n+m+1;j++)
        if (fabs(a[j][i])>fabs(a[mx][i])) mx=j;
        if (i!=mx) swap(a[i],a[mx]);
        for (int j=i+1;j<=n+m+1;j++)
        {
            double t=a[j][i]/a[i][i];
            for (int k=i;k<=n+m+2;k++)
            a[j][k]-=t*a[i][k];
        }
    }
}
int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    n=read(),m=read();cin>>p;
    a[0][0]=p;a[0][1]=1-p;a[0][0]--;a[0][n+m+2]--;
    for (int i=1;i<n+m;i++)
    a[i][i-1]=p,a[i][i+1]=1-p,a[i][i]--,a[i][n+m+2]--;
    a[n+m][n+m]=1-p;a[n+m][n+m-1]=p;a[n+m][n+m]--,a[n+m][n+m+2]--;
    a[n][n-1]=a[n][n+1]=a[n][n+m+2]=0;
    a[n+m+1][n-1]=p,a[n+m+1][n+1]=1-p,a[n+m+1][n+m+1]--,a[n+m+1][n+m+2]--;
    gauss();
    printf("%.7lf",a[n+m+1][n+m+2]/a[n+m+1][n+m+1]);
    return 0;
}

　　C：考虑团中编号最大的点，只要找到其中包含关系就行了。可以发现若i>j，i向j有边，只要j在i所连点中的排名和其度数-1相同，j就是被包含的。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
#define N 1000010
int n,m,degree[N],ans=0;
bool flag[N];
vector<int> a[N];
int main()
{
    freopen("network.in","r",stdin);
    freopen("network.out","w",stdout);
    n=read(),m=read();
    for (int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        a[y].push_back(x);degree[y]++;
    }
    for (int i=1;i<=n;i++)
    {
        sort(a[i].begin(),a[i].end());
        degree[i]=unique(a[i].begin(),a[i].end())-a[i].begin();
    }
    for (int i=1;i<=n;i++) flag[i]=1;
    for (int i=n;i;i--)
    if (flag[i])
    {
        ans++;
        for (int j=0;j<degree[i];j++)
        if (degree[a[i][j]]==j) flag[a[i][j]]=0;
    }
    cout<<ans;
    return 0;
}

　　result：240 rank1