zoj2930
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <iomanip> #include <cstring> #include <map> #include <queue> #include <set> #include <cassert> #include <stack> #include <bitset> #define mkp make_pair using namespace std; const double EPS=1e-12; typedef long long lon; const lon SZ=210,SSZ=210,APB=10000,one=1,INF=0x7FFFFFFF,mod=1000000007; int n,m,S=207,T=208,mp[SZ][SZ]; int dep[SZ]; void init() { for(int i=1;i<=n;++i) { int tmp; cin>>tmp; mp[i][T]=tmp; } for(int i=1;i<=n;++i) { int tmp; cin>>tmp; mp[S][i]=tmp; } cin>>m; for(int i=1;i<=m;++i) { int a,b; cin>>a>>b; mp[b][a]=INF; } } bool bfs() { memset(dep,0,sizeof(dep)); dep[S]=1; queue<int> q; q.push(S); for(;q.size();) { int fr=q.front(); q.pop(); for(int i=1;i<=T;++i) { if(!dep[i]&&mp[fr][i]) { dep[i]=dep[fr]+1; q.push(i); if(i==T)return 1; } } } return 0; } int dinic(int x,int flow) { if(x==T)return flow; else { int rem=flow; for(int i=1;i<=T&&rem;++i) { if(dep[i]==dep[x]+1&&mp[x][i]) { int tmp=dinic(i,min(rem,mp[x][i])); if(!tmp)dep[i]=0; rem-=tmp; mp[x][i]-=tmp,mp[i][x]+=tmp; } } return flow-rem; } } bool vst[SZ]; void work() { int res=0,ans=0; for(;bfs();)res+=dinic(S,INF); queue<int> q; for(int i=1;i<=n;++i) { if(mp[i][T]) { vst[i]=1; q.push(i); } } for(;q.size();) { int fr=q.front(); q.pop(); for(int i=1;i<=n;++i) { if(mp[i][fr]&&!vst[i]) { vst[i]=1; q.push(i); } } } for(int i=1;i<=n;++i)if(vst[i])++ans; cout<<res<<" "<<n-ans<<endl; } void release() { memset(mp,0,sizeof(mp)); memset(vst,0,sizeof(vst)); } int main() { std::ios::sync_with_stdio(0); //freopen("d:\\1.txt","r",stdin); //cout<<(1<<31)<<endl; int casenum; //cin>>casenum; //cout<<casenum<<endl; //for(int time=1;time<=casenum;++time) for(int time=1;cin>>n;++time) { init(); work(); release(); } return 0; }
各点向S连推迟的花费,向T连提前的花费,S表示提前,T表示推迟。a推迟b也推迟b往a连INF。最小割后从各点出发,能直接或间接到T的就是必须推迟的,剩下的就是能提前的。
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

更多精彩