原题地址：点击打开链接
Foed-Fulkerson算法会超时，这里我们用Dinic算法
#include<stdio.h> #include<string.h> #include<queue> using namespace std; int map[700][700],len[700],pos[700]; #define min(x,y)(x<y?x:y) bool bfs(int s,int t) //分层 { int i; memset(len,-1,sizeof(len)); queue<int>que; que.push(s); len[s]=0; while(!que.empty()) { int u=que.front(); que.pop(); for(i=0;i<=t;i++) { if(map[u][i]>0 && len[i]<0) { len[i]=len[u]+1; que.push(i); } } } if(len[t]>-1) return true; return false; } int dfs(int u,int t,int f) //寻找增广路 { if(u==t) return f; for(int &i=pos[u];i<=t;i++) //注意该处的引用，意思就是从上次遍历过的地方开始 { if(map[u][i]>0 && len[u]<len[i]) { int d=dfs(i,t,min(map[u][i],f)); if(d>0) { map[u][i]-=d; map[i][u]+=d; return d; } } } return 0; } int max_flow(int s,int t) { int res=0; while(bfs(s,t)) { memset(pos,0,sizeof(pos)); while(1) { int d=dfs(s,t,99999); if(d<=0) break; res+=d; } } return res; } int main() { int i,j,c,x,m,n,s,t,sum1,sum2; //s源点 t汇点 scanf("%d",&c); while(c--) { s=0; sum1=0; sum2=0; memset(map,0,sizeof(map)); scanf("%d%d",&m,&n); t=m+n+1; for(i=1;i<=m;i++) { scanf("%d",&x); sum1+=x; map[s][i]=x; } for(i=1;i<=n;i++) { scanf("%d",&x); sum2+=x; map[m+i][t]=x; } if(sum1!=sum2) { printf("Terrible\n"); continue; } for(i=1;i<=m;i++) for(j=m+1;j<=m+n;j++) map[i][j]=1; int res=max_flow(s,t); if(res==sum1) printf("Not Sure\n"); else printf("Terrible\n"); } return 0; }