题目：https://www.luogu.org/problemnew/show/P5061
就是建出补图来，二分图染色。
做DP，f[ i ]表示一个队里人数是否能达到 i 人。如果图合法，能达到 i 人的话一定能达到 n-i 人。因为初值是 f[ 0 ] = 1 ，所以别用 f[ 0 ] 判断，对于这中情况用 f[ n ] 判断就行了。
如果图不合法，不知道第三问是什么意思了。（反正2组分不下，那就默契的两个人在一组，剩下的人一人一组还不行？）不过好像输出 m 就行了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=2505,mod=1e9+7; int n,m,dfn[N],tot,cl[3],col[N],bin[N]; bool b[N][N],flag,f[N]; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret; } void dfs(int cr) { dfn[cr]=tot;cl[col[cr]]++; for(int i=1;i<=n;i++) if(!b[i][cr]) { if(col[i]&&col[i]==col[cr]){flag=1;return;} if(!col[i])col[i]=3-col[cr], dfs(i); } } int main() { n=rdn(); m=rdn(); for(int i=1,u,v;i<=m;i++) { u=rdn(); v=rdn(); b[u][v]=b[v][u]=1; } for(int i=1;i<=n;i++)b[i][i]=1; f[0]=1; for(int i=1;i<=n;i++) if(!col[i]) { tot++;cl[1]=cl[2]=0;col[i]=1;dfs(i); if(flag)break; for(int j=n;j>=0;j--) { if(j-cl[1]>=0)f[j]|=f[j-cl[1]]; if(j-cl[2]>=0)f[j]|=f[j-cl[2]]; } } if(flag){printf("-1 %d ",m);return 0;} bin[0]=1;for(int i=1;i<=n;i++)bin[i]=((ll)bin[i-1]<<1)%mod; int ans=0,prn=0; for(int i=(n+1)>>1;i<=n;i++) if(f[i]) { ans++; if(!prn)prn=i; } prn=bin[prn]-bin[n-prn];if(prn<0)prn+=mod; printf("%d %d ",ans,prn); ans=0; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(b[i][j]&&dfn[i]==dfn[j]&&col[i]!=col[j])ans++; printf("%d ",ans); return 0; }