BZOJ3876
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <cmath> #include <vector> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define EE 40000 #define N 350 #define source 0 #define sink N-1 struct Tedge { int to,flow,val; }edge[EE]; #define E edge[i] #define FLOW E.flow #define TO E.to #define VAL E.val int fst[N],NXT[EE],e_tot; int n; void add_e(int from,int to,int flow,int val) { static int &i=e_tot; TO=to; FLOW=flow; VAL=val; NXT[i]=fst[from]; fst[from]=i++; TO=from; FLOW=0; VAL=-val; NXT[i]=fst[to]; fst[to]=i++; } void init() { int _,__,___; memset(fst,-1,sizeof(fst)); read(n); for(int i=1;i<=n;i++) { read(_); if(i!=1)add_e(i,1,INF,0); if(_==0) continue; add_e(i,sink,_,0); while(_--) { read(__); read(___); add_e(i,__,INF,___); add_e(source,__,1,___); } } } int S,T,ans; int d[N],p[N]; bool inq[N]; void Augment() { // puts("1"); static int node,c,i; node=T; c=INF; while(node!=S) { i=p[node]; c=min(FLOW,c); node=edge[i^1].to; } node=T; while(node!=S) { i=p[node]; FLOW-=c; i^=1; FLOW+=c; node=TO; } ans+=c*d[T]; } bool SPFA() { static int Q[65540],x,i; static unsigned short int he=0,ta=0; memset(d,0x7f,sizeof(d)); d[S]=0; inq[S]=true; Q[++he]=S; while(he!=ta) { x=Q[++ta]; inq[x]=0; for(i=fst[x];~i;i=NXT[i]) if(FLOW&&d[TO]>d[x]+VAL) { d[TO]=d[x]+VAL; p[TO]=i; if(!inq[TO]) inq[TO]=1,Q[++he]=TO; } } return d[T]<INF; } int main() { init(); S=source; T=sink; while(SPFA()) Augment(); printf("%d",ans); return 0; } |
BZOJ2502
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 |
#include <cstdio> #include <algorithm> #include <cstring> #include <queue> #define ll long long #define INF 10000000 #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } void cp(int &x,int y) { x>y?x=y:x=x; } using namespace std; #define EE 40000 #define N 150 #define source 0 #define sink (N-1) #define sink_ (N-2) #define source_ (N-3) struct Tedge { int to,flow; }edge[EE]; int e_tot,fst[N],nxt[EE]; #define E edge[i] #define FLOW E.flow #define TO E.to #define NXT nxt[i] void add_e(int from,int to,int flow) { static int &i=e_tot; FLOW=flow; TO=to; NXT=fst[from]; fst[from]=i++; FLOW=0; TO=from; NXT=fst[to]; fst[to]=i++; } int o[N],n; void init() { memset(fst,-1,sizeof(fst)); int _,__; read(n); For(i,1,n) { add_e(source,i,INF); read(_); o[i]-=_; if(_==0) add_e(i,sink,INF); while(_--) { read(__); o[__]++; add_e(i,__,INF); } } For(i,1,n) { if(o[i]<0) add_e(i,sink_,-o[i]); else add_e(source_,i,o[i]); } } int m[N],d[N],p[N],cur[N],S,T; bool bfs() { static queue <int> Q; static int x,i; Q.push(T); d[T]=1; while(!Q.empty()) { x=Q.front(); Q.pop(); m[d[x]]++; for(i=fst[x];~i;i=NXT) if((edge[i^1].flow)&&!d[TO]) { d[TO]=d[x]+1; Q.push(TO); } } return d[S]; } void Augment() { static int node,c,i; node=T; c=INF; while(node!=S){ i=p[node]; cp(c,FLOW); node=edge[i^1].to; } node=T; while(node!=S) { i=p[node]; FLOW-=c; i^=1; FLOW+=c; node=TO; } return; } void ISAP() { memset(m,0,sizeof(m)); memset(d,0,sizeof(d)); int node=S,M,i; bool flag; For(i,0,N-1) cur[i]=fst[i]; while(d[S]<=n+4) { if(node==T) { Augment(); node=S; } flag=false; for(i=cur[node];~i;i=NXT) if(d[TO]==d[node]-1&&FLOW) { p[TO]=i; cur[node]=i; node=TO; flag=true; break; } if(flag) continue; if(!--m[d[node]]) return; M=N-1; for(cur[node]=i=fst[node];~i;i=NXT) if(FLOW) cp(M,d[TO]+1); m[d[node]=M]++; node=(node!=S?edge[p[node]^1].to:node); } } int main() { freopen("BZOJ2502.in","r",stdin); init(); S=source_; T=sink_; ISAP(); add_e(sink,source,INF); ISAP(); printf("%d\n",edge[e_tot-1].flow); return 0; } |
BZOJ2055
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <cmath> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } void cp(int &x,int y) { x>y?x=y:x; } using namespace std; #define EE 80010 #define N 210 #define source 0 #define sink (N-1) #define source_ (N-2) #define sink_ (N-3) #define calc(i) (i+n) struct Tedge { int to,flow,val; }edge[EE]; int fst[N],nxt[EE],e_tot; #define E edge[i] #define FLOW E.flow #define TO E.to #define VAL E.val #define NXT nxt[i] void add_e(int from,int to,int flow,int val) { static int &i=e_tot; TO=to; FLOW=flow; VAL=val; NXT=fst[from]; fst[from]=e_tot++; TO=from; FLOW=0; VAL=-val; NXT=fst[to]; fst[to]=e_tot++; } int n,m,v[N]; void init() { int _; memset(fst,-1,sizeof(fst)); read(n); read(m); add_e(sink,source,m,0); for(int i=1;i<=n;i++) { add_e(source,i,INF,0); add_e(calc(i),sink,INF,0); read(_); add_e(source_,calc(i),_,0); add_e(i,sink_,_,0); } For(i,1,n-1) for(int j=i+1;j<=n;j++) { read(_); if(!~_) continue; add_e(calc(i),j,INF,_); } } int ans,d[N],p[N],S,T; bool inq[N]; void Augment() { static int node,c,i; node=T; c=INF; while(node!=S) { i=p[node]; cp(c,FLOW); node=edge[i^1].to; } node=T; while(node!=S) { i=p[node]; FLOW-=c; i^=1; FLOW+=c; node=TO; } ans+=c*d[T]; } bool SPFA() { static int Q[65540],i; static unsigned short int he=0,ta=0,x; memset(d,0x7f,sizeof(d)); Q[++he]=S; d[S]=0; while(he!=ta) { x=Q[++ta]; inq[x]=false; for(i=fst[x];~i;i=NXT) if(FLOW&&d[TO]>d[x]+VAL) { d[TO]=d[x]+VAL; p[TO]=i; if(!inq[TO]) inq[TO]=true,Q[++he]=TO; } } if(d[T]>INF) return false; Augment(); return true; } int main() { init(); S=source_; T=sink_; while(SPFA()); printf("%d",ans); return 0; } |