题目：
就是建出补图来，二分图染色。
做DP，f[ i ]表示一个队里人数是否能达到 i 人。如果图合法，能达到 i 人的话一定能达到 n-i 人。因为初值是 f[ 0 ] = 1 ，所以别用 f[ 0 ] 判断，对于这中情况用 f[ n ] 判断就行了。
如果图不合法，不知道第三问是什么意思了。（反正2组分不下，那就默契的两个人在一组，剩下的人一人一组还不行？）不过好像输出 m 就行了。
#include#include #include #include #define ll long longusing 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\n%d\n",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\n",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\n",ans); return 0;}