大概就是让你求一般图的最大团。
直接随机化。然后我们把点序当 PEO 打乱，假装第一个点在最大团里。
然后就判一下其余点的连通就好了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<cstdlib> #include<iterator> #include<queue> #include<vector> #include<map> #include<set> #define ll long long using namespace std; int n,ans,G[55][55]; int at=1,ptr[110]; int per[110]; bool vis[110]; template<typename int_t> void readx(int_t& x) { x=0; int_t k=1; char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } void Randomize() { for (int i=1;i<=n;i++) swap(per[i],per[rand()%i+1]); } void Process() { memset(vis,0,sizeof vis); int tmp=0; for (int i=1;i<=n;i++) if (!vis[i]) { tmp++; for (int j=i+1;j<=n;j++) if (!G[per[i]][per[j]]) vis[j]=1; } ans=max(ans,tmp); } int main() { srand(20010929); readx(n); int fx,tx; while (scanf("%d%d",&fx,&tx)!=EOF) G[tx][fx]=G[fx][tx]=1; for (int i=1;i<=n;i++) per[i]=i; for (int w=1;w<=10000;w++) { Randomize(); Process(); } printf("%d\n",ans); } |