题目大意：有一个人想去拍电影，有n部电影，每部电影有可以拍摄的时间和期限，问最后能否拍完所有电影；
题目解析：构图，超级源指向n部电影，每部电影指向可以拍摄的时间，容量为1，最后把所有的时间都指向超级汇；
AC代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<queue> using namespace std; const int inf=0x3fffffff; const int maxn=410; struct node { int to,cap,rev; node(int a,int b,int c) { to=a; cap=b; rev=c; } }; vector<node>vec[maxn]; int pre[maxn],iter[maxn]; bool vis[maxn]; void add_edge(int from,int to,int cost) { vec[from].push_back(node(to,cost,vec[to].size())); vec[to].push_back(node(from,0,vec[from].size()-1)); } void bfs(int s){ memset(pre,-1,sizeof(pre)); queue<int>que; pre[s]=0;que.push(s); while(!que.empty()){ int v=que.front();que.pop(); for(int i=0;i<vec[v].size();i++){ node &e=vec[v][i]; if(e.cap>0&&pre[e.to]<0){ pre[e.to]=pre[v]+1; que.push(e.to); } } } } int dfs(int v,int t,int f){ if(v==t) return f; for(int &i=iter[v];i<vec[v].size();i++){ node &e=vec[v][i]; if(e.cap>0&&pre[v]<pre[e.to]){ int d=dfs(e.to,t,min(f,e.cap)); if(d>0){ e.cap-=d; vec[e.to][e.rev].cap+=d; return d; } } } return 0; } int max_flow(int u,int v) { int flow=0; while(1) { bfs(u); if(pre[v]<0) return flow; memset(iter,0,sizeof(iter)); int f; while((f=dfs(u,v,inf))>0) flow+=f; } } int main() { int n,i,j,f,d,t,k,w,sum,a[10]; char str[1001]; scanf("%d",&t); while(t--) { memset(vis,0,sizeof(vis)); sum=0; scanf("%d",&n); for(i=0;i<maxn;i++) vec[i].clear(); for(i=1;i<=n;i++) { for(j=1;j<=7;j++) scanf("%d",&a[j]); scanf("%d%d",&d,&w); sum+=d; add_edge(0,i,d); for(j=1;j<=7;j++) { if(a[j]==0) continue; for(k=0;k<w;k++) { add_edge(i,n+k*7+j,1); vis[n+7*k+j]=1; } } } for(i=0;i<maxn;i++) { if(vis[i]) add_edge(i,407,1); } if(max_flow(0,407)==sum) printf("Yes\n"); else printf("No\n"); } return 0; }
