二分t+最大权闭合图。
很显然二分那个t作为limit。每一个limit下，有一些边不能用了，然后要知道这种情况下怎么选点获得的价值最大。
这么想：一个shop想获得收益，就必须选择某一些plant，问题就转化成了最大权闭合图。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } template <class T> inline void read(T &x) { char c = getchar(); x = 0;while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } } int T,n,m; int L; struct X { int pay; int t; }p[300]; vector<int>g[300]; int pro[300]; bool flag[300],se[300]; const int maxn = 3000 + 10; const int INF = 0x7FFFFFFF; struct Edge { int from, to, cap, flow; Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f){} }; vector<Edge>edges; vector<int>G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; int s, t; void init() { for (int i = 0; i < maxn; i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); int w = edges.size(); G[from].push_back(w - 2); G[to].push_back(w - 1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue<int>Q; Q.push(s); d[s] = 0; vis[s] = 1; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = 0; i<G[x].size(); i++) { Edge e = edges[G[x][i]]; if (!vis[e.to] && e.cap>e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a) { if (x == t || a == 0) return a; int flow = 0, f; for (int &i = cur[x]; i<G[x].size(); i++) { Edge e = edges[G[x][i]]; if (d[x]+1 == d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0) { edges[G[x][i]].flow+=f; edges[G[x][i] ^ 1].flow-=f; flow+=f; a-=f; if(a==0) break; } } if(!flow) d[x] = -1; return flow; } int dinic(int s, int t) { int flow = 0; while (BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow; } int check(int limit) { memset(flag,0,sizeof flag); memset(se,0,sizeof se); for(int i=1;i<=n;i++) if(p[i].t<=limit) flag[i]=1; init(); s=0; t=n+m+1; int sum=0; for(int i=1;i<=m;i++) { bool fail=0; for(int j=0;j<g[i].size();j++) if(flag[g[i][j]]==0) fail=1; if(fail==1) continue; for(int j=0;j<g[i].size();j++) AddEdge(i,g[i][j]+m,INF); AddEdge(s,i,pro[i]); sum=sum+pro[i]; } for(int i=1;i<=n;i++) AddEdge(i+m,t,p[i].pay); return sum-dinic(s,t); } int main() { //File(); scanf("%d",&T); int cas=1; while(T--) { scanf("%d%d%d",&n,&m,&L); for(int i=0;i<=m;i++) g[i].clear(); for(int i=1;i<=n;i++) scanf("%d%d",&p[i].pay,&p[i].t); for(int i=1;i<=m;i++) { scanf("%d",&pro[i]); int k; scanf("%d",&k); while(k--) { int x; scanf("%d",&x); g[i].push_back(x); } } int left=0,right=1000000000; int ans1=-1,ans2=-1; while(left<=right) { int mid=(left+right)/2; int ppp=check(mid); if(ppp>=L) { right=mid-1; ans1=mid; ans2=ppp; } else left=mid+1; } printf("Case #%d: ",cas++); if(ans1==-1) printf("impossible "); else printf("%d %d ",ans1,ans2); } return 0; }