ZOJ 1015 Fishing Net（弦图判定）

2021-06-12 05:08

阅读：612

标签：pac long ack problem push vector ext ons freopen

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=15

题意：

判断是否是弦图。

思路：

所谓弦图，也就是对于一个无向图，若该图的任意一个长度大于3的环中存在一条边连接这个环上不相邻的两点，则此图称作弦图。

弦图的判断不难，先用最大势算法计算出完美消除序列，然后用完美消除序列判断原图是否是弦图，如何从完美消除序列判断原图是不是弦图？最朴素的办法是依次判断 {vi+1,…,vn}中所有与vi相邻的点是否构成了一个团。可以这样优化：设{vi+1,…,vn}中所有与vi相邻的点依次为 vj1,……,vjk。只需判断vj1是否与vj2,……,vjk相邻即可。

 1 #include 2 #include
 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include10 #include11 #includeset>
12 using namespace std;
13 typedef long long ll;
14 typedef pairint,ll> pll;
15 const int INF = 0x3f3f3f3f;
16 const int maxn=1000+5;
17 
18 int n, m;
19 int tot;
20 int head[maxn];
21 int label[maxn]; //label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号
22 int vis[maxn];
23 int q[maxn];
24 int mp[maxn][maxn];
25 
26 struct node
27 {
28     int v;
29     int next;
30 }e[maxn*maxn+5];
31 
32 void addEdge(int u, int v)
33 {
34     e[tot].v=v;
35     e[tot].next=head[u];
36     head[u]=tot++;
37 }
38 
39 void MCS()  //最大势算法
40 {
41     memset(vis,0,sizeof(vis));
42     memset(label,0,sizeof(label));
43     for(int i=n;i;i--)
44     {
45         int pos=0;
46         for(int j=1;j//选择当前未访问且label值最大的
47             if(!vis[j] && label[j]>=label[pos])   pos=j;
48         vis[pos]=1;
49         q[i]=pos;
50         for(int j=head[pos];j!=-1;j=e[j].next)  //与pos结点相邻的结点label值+1
51             label[e[j].v]++;
52     }
53 }
54 
55 bool check()
56 {
57     for(int i=1;i)
58     {
59         vectorint> v;
60         for(int j=i+1;j)
61             if(mp[q[i]][q[j]]==1)  v.push_back(q[j]);
62         for(int j=1;j)
63             if(mp[v[0]][v[j]]==0)  return false;
64     }
65     return true;
66 }
67 
68 int main()
69 {
70     //freopen("in.txt","r",stdin);
71     while(scanf("%d%d",&n,&m)!=EOF)
72     {
73         if(n==0 && m==0)  break;
74         tot=0;
75         memset(head,-1,sizeof(head));
76         memset(mp,0,sizeof(mp));
77         while(m--)
78         {
79             int u,v;
80             scanf("%d%d",&u,&v);
81             addEdge(u,v);
82             addEdge(v,u);
83             mp[u][v]=mp[v][u]=1;
84         }
85         MCS();
86         if(check()==true) puts("Perfect\n");
87         else puts("Imperfect\n");
88     }
89     return 0;
90 }

ZOJ 1015 Fishing Net（弦图判定）

标签：pac long ack problem push vector ext ons freopen

原文地址：http://www.cnblogs.com/zyb993963526/p/7289569.html

上一篇：HTML5基础知识汇总_(2)自己定义属性及表单新特性

下一篇：windows下Docker的安装

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：ZOJ 1015 Fishing Net（弦图判定）
文章链接：http://soscw.com/index.php/essay/93815.html

亲，登录后才可以留言！

ZOJ 1015 Fishing Net（弦图判定）

评论

热门文章

推荐文章

最新文章

置顶文章