第一问: 网络流,这并没有什么问题
第二问: 阿丽和桃子的游戏,这并没有什么问题
总之是傻逼了
//coder : davidwang #include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <algorithm> #include <vector> #include <bitset> using namespace std; #define LL long long #define X first #define Y second inline int read() { int ret=0,f=1; char ch; for (ch=getchar();ch<'0' || ch>'9';ch=getchar()) if (ch=='-') f=-f; for (;'0'<=ch && ch<='9';ch=getchar()) ret=ret*10+ch-'0'; return ret*f; } const int N = 210; struct edge{ int to,flow; edge(int to=0,int flow=0): to(to),flow(flow){} }e[N*N*2]; int d[N],f[N*N*2],x[N],n,m,cnt,q[N]; vector<int>g[N]; bitset<N*N>A; inline void connect(int a,int b,int f){ e[cnt]=edge(b,f); g[a].push_back(cnt++); x[a]++; e[cnt]=edge(a,f); g[b].push_back(cnt++); x[b]++; } int s=1,t=2; inline int bfs() { int head=0,tail=1,u,v; for (int i=1;i<=n;i++) d[i]=0; d[s]=1; q[1]=s; while (head<tail){ u=q[++head]; for (vector<int>::iterator it=g[u].begin();it!=g[u].end();it++){ if (e[*it].flow && !d[e[*it].to]){ q[++tail]=e[*it].to; d[e[*it].to]=d[u]+1; } } } return d[t]; } inline int dfs(int x,int flow){ if (x==t || flow==0) return flow; int totflow=0,f; for (vector<int>::iterator it=g[x].begin();it!=g[x].end();it++){ if (e[*it].flow && d[e[*it].to]==d[x]+1){ f=dfs(e[*it].to,min(flow,e[*it].flow)); flow-=f; totflow+=f; e[*it].flow-=f; e[(*it)^1].flow+=f; if (flow==0) return totflow; } } if (flow) d[x]=-1; return totflow; } inline void work() { int ans1=0,ans2=0; n=read(); m=read(); cnt=0; for (int i=1;i<=n;i++){ g[i].clear(); x[i]=0; } int cE=m; for (int i=1;i<=m;i++){ int x=read(),y=read(); if (x+y==3) cE--; else connect(x,y,1); } for (int i=0;i<=m*2;i++) A[i]=0; A[x[1]]=1; while (bfs()) ans1+=dfs(s,INT_MAX); printf("%d ",cE-ans1); for (int i=3;i<=n;i++){ A=(A<<x[i]|A); } for (int i=0;i<=cE;i++){ if (A[cE+i]==1 || A[cE-i]==1){ printf("%d\n",i); break; } } } int main() { #ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); #endif int T=read(); while (T--) work(); return 0; }