【图论专题三】【NOI2016模拟6.20】没有强联通分量的无聊世界

本文主要是介绍【图论专题三】【NOI2016模拟6.20】没有强联通分量的无聊世界，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【NOI2016模拟6.20】没有强联通分量的无聊世界

Description

在这里插入图片描述
Input

Output

在这里插入图片描述
Sample Input
3 4
1 2
1 3
2 3
3 1

Sample Output
1

Data Constraint
在这里插入图片描述

题解

可以将它拓扑出来，然后然后~~
就没有然后了
所以，我们要换一种思路。
注意性质 DAG的性质是：一个点的拓扑序只会向比它编号大连边。所以我们只需要求出一个编号的顺序，然后可以计算代价。这就是基本思路。

第一种方法

我们可以全排列顺序，然后贪心计算代价（应该很简单吧）。取最小值就好了。
预计分数：20分

第二种方法

我们可以状态压缩全排列选择的编号。因为编号的顺序与加入一个编号的答案不产生影响，所以自然可行
预计分数：60分。

第三种方法

对第二种方法进行优化，用位运算、预处理等加速算法二。
预计分数：100分

代码

第二种方法

#include<cstdio>
#include<cstring>
#define N 23
#define M 485
#define MAX_f 4194305
using namespace std;
int n,m,total1;
int th2[N],next[M],head[M],edge[M],f[MAX_f];
bool used[MAX_f];
void insert(int x,int y)
{total1++;next[total1]=head[x];head[x]=total1;edge[total1]=y;
}
int main()
{freopen("dizzycows.in","r",stdin);freopen("dizzycows.out","w",stdout);scanf("%d%d",&n,&m);th2[0]=1;for (int i=1;i<=n;i++){th2[i]=th2[i-1]*2;}for (int i=1;i<=m;i++){int x,y;scanf("%d%d\n",&x,&y);insert(x,y);}f[0]=0;for (int i=1;i<=th2[n];i++){f[i]=-999999;}memset(used,false,sizeof(used));for (int i=0;i<=n-1;i++){for (int j=0;j<=th2[n];j++){if (f[j]>=0&&used[j]==false){used[j]=true;for (int k=1;k<=n;k++){if ((j&th2[k-1])==0){int p=j|th2[k-1];int cost=0;for (int i1=head[k];i1;i1=next[i1]){int y=edge[i1];if ((j&th2[y-1])!=0) cost++;}if (f[p]<f[j]+cost){f[p]=f[j]+cost;}}}}}}printf("%d",m-f[th2[n]-1]);
}

第三种方法

#include<cstdio>
#include<cstring>
#define N 23
#define M 485
#define MAX_f 4194305
using namespace std;
int n,m,total1;
int q[N],th2[N],next[M],head[M],edge[M],f[MAX_f],h[MAX_f];
bool used[MAX_f],bz[N][N];
void insert(int x,int y)
{total1++;next[total1]=head[x];head[x]=total1;edge[total1]=y;
}
void zhuan(int k)
{h[k]=0;int q=k;int number=0;while (q>0){if (q%2==1){h[k]++;}number++;q=q/2;}
}
int main()
{freopen("dizzycows.in","r",stdin);freopen("dizzycows.out","w",stdout);scanf("%d%d",&n,&m);th2[0]=1;for (int i=1;i<=n;i++){th2[i]=th2[i-1]*2;}for (int i=0;i<=th2[n]-1;i++){zhuan(i);}memset(bz,false,sizeof(bz));for (int i=1;i<=m;i++){int x,y;scanf("%d%d\n",&x,&y);q[x]=q[x]+th2[y-1];}f[0]=0;for (int i=1;i<=th2[n]-1;i++){f[i]=-999999;}memset(used,false,sizeof(used));int po=0;for (int i=0;i<=n-1;i++){for (int j=0;j<=th2[n]-1;j++){if (f[j]>=0&&used[j]==false){used[j]=true;for (int k=1;k<=n;k++){if ((j&th2[k-1])==0){int p=j|th2[k-1];int cost=0;cost=h[(q[k]&j)];if (f[p]<f[j]+cost){f[p]=f[j]+cost;}}}}}}printf("%d",m-f[th2[n]-1]);
}