思路清奇的一道题
READ MORE →
BZOJ4808
题目名字很有趣
但是看完题面会发现这就是个黑白染色最小割
网络流大法好，ISAP直接跑
好像这几道题是一个系列的233
|
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 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 |
#include <cstdio> #include <algorithm> #include <cstdlib> #include <cstring> #include <queue> #define ll long long #define INF 1000000000 char cc; int C; #define p(x) ('0'<=x&&x<='9') template <class T> void read( T &x ) { cc=getchar(); C=1; x=0; 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 N 205 #define E 800000 #define S 0 #define T 40009 struct Tedge { int from,to,cap,flow; }edge[E]; int e_tot,NXT[E],fst[40010]; #define TO edge[i].to #define FROM edge[i].from #define FL (edge[i].cap-edge[i].flow) void add_e(int _,int __,int cap) { edge[e_tot].from=_; edge[e_tot].to=__; edge[e_tot].cap=cap; edge[e_tot].flow=0; NXT[e_tot]=fst[_]; fst[_]=e_tot++; edge[e_tot].from=__; edge[e_tot].to=_; edge[e_tot].cap=cap; edge[e_tot].flow=cap; NXT[e_tot]=fst[__]; fst[__]=e_tot++; } int d[40010],p[40010],cur[40010],cnt[40010]; int mp[N][N],n,m,tot; bool bfs() { int x,i; d[T]=1; queue <int> Q; Q.push(T); while(!Q.empty()) { x=Q.front(); Q.pop(); cnt[d[x]]++; for(i=fst[x];~i;i=NXT[i]) { if(d[TO]||FL) continue; d[TO]=d[x]+1; Q.push(TO); } } return d[S]!=0; } int Augment() { int node,ret,i; node=T; ret=INF; while(node!=S) { i=p[node]; ret=min(ret,FL); node=FROM; } node=T; while(node!=S) { i=p[node]; edge[i].flow+=ret; edge[i^1].flow-=ret; node=FROM; } return ret; } int ISAP() { if(!bfs()) return 0; int node=S,ret=0,M,i; bool flag; for(int i=0;i<40010;i++) cur[i]=fst[i]; while(d[S]<=tot+2) { if(node==T) { ret+=Augment(); node=S; } flag=false; for(i=cur[node];~i;i=NXT[i]) if(d[TO]==d[node]-1&&FL) { flag=true; p[TO]=cur[node]=i; node=TO; break; } if(flag) continue; M=tot+5; for(cur[node]=i=fst[node];~i;i=NXT[i]) if(FL) M=min(M,d[TO]+1); if(!--cnt[d[node]]) return ret; cnt[d[node]=M]++; node!=S?node=edge[p[node]].from:node=S; } return ret; } const int _x[8]={1,1,2,2,-1,-1,-2,-2},_y[8]={2,-2,1,-1,2,-2,1,-1}; #define calc(x,y) ( (x-1)*m+y ) void pre() { memset(fst,-1,sizeof(fst)); read(n); read(m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(mp[i][j]); int x,y,pt; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(mp[i][j]) continue; tot++; pt=calc(i,j); if((i^j)&1) { add_e(S,pt,1); for(int k=0;k<8;k++) { x=_x[k]+i; y=_y[k]+j; if(mp[x][y])continue; if(x>n||x<=0||y>m||y<=0) continue; add_e(pt,calc(x,y),INF); } } else add_e(pt,T,1); } } int main() { // freopen("BZOJ4808.in","r",stdin); pre(); printf("%d",tot-ISAP()); return 0; } |
BZOJ1324
有些炸裂的题解
题目是一道最大点独立集，比较裸的那种
最大点独立集=最小点覆盖集的补集
然后套最小点覆盖集用sum-tot_flow即可
|
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 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #include <queue> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') 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 E 100010 #define N 10050 struct Tedge { int from,to,cap,flow; }edge[E]; #define TO edge[i].to #define FROM edge[i].from #define FLO (edge[i].cap-edge[i].flow) int e_tot,fst[N],NXT[E]; #define calc(x,y) ((x-1)*m+y) #define S 0 #define T N-1 void add_e(int _,int __,int ___) { edge[e_tot].to=__; edge[e_tot].from=_; edge[e_tot].cap=___; edge[e_tot].flow=0; NXT[e_tot]=fst[_]; fst[_]=e_tot++; edge[e_tot].to=_; edge[e_tot].from=__; edge[e_tot].cap=___; edge[e_tot].flow=___; NXT[e_tot]=fst[__]; fst[__]=e_tot++; } int dist[N],cnt[N],cur[N],p[N]; bool bfs() { int x; queue <int> Q; dist[T]=1; cnt[1]=1; Q.push(T); while(!Q.empty()) { x=Q.front(); Q.pop(); for(int i=fst[x];~i;i=NXT[i]) { if(dist[TO]||FLO) continue; cnt[dist[TO]=dist[x]+1]++; Q.push(TO); } } return dist[S]!=0; } int Augment() { static int ret,node,i; ret=INF; node=T; while(node!=S) { i=p[node]; ret=min(ret,FLO); node=FROM; } node=T; while(node!=S) { i=p[node]; edge[i].flow+=ret; edge[i^1].flow-=ret; node=FROM; } return ret; } int ISAP() { if(!bfs()) return 0; int node=S,ret=0; bool flag; for(int i=0;i<N;i++) cur[i]=fst[i]; while(dist[S]<N) { if(node==T) { ret+=Augment(); node=S; } flag=false; for(int i=cur[node];~i;i=NXT[i]) { if(dist[TO]!=dist[node]-1||!FLO) continue; flag=true; p[TO]=i; cur[node]=i; node=TO; break; } if(flag) continue; int M=N+5; cur[node]=fst[node]; for(int i=fst[node];~i;i=NXT[i]) { if(!FLO) continue; M=min(dist[TO]+1,M); } if(!--cnt[dist[node]]) return ret; dist[node]=M; cnt[M]++; if(node!=S) node=edge[p[node]].from; } return ret; } int a[105][105],tot,n,m; const int _x[4]={0,0,1,-1},_y[4]={1,-1,0,0}; void pre() { memset(fst,-1,sizeof(fst)); read(n); read(m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(a[i][j]),tot+=a[i][j]; int _,__; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { if((i^j)&1) { add_e(calc(i,j),T,a[i][j]); continue; } add_e(S,calc(i,j),a[i][j]); for(int k=0;k<4;k++) { _=i+_x[k]; __=j+_y[k]; if(_<=0||_>n||__<=0||__>m) continue; add_e(calc(i,j),calc(_,__),INF); } } } int main() { pre(); printf("%d",tot-ISAP()); return 0; } |
BZOJ1497
最小割
从源点向每个人连收益大小的边
人向站连大小为INF的边
站向汇连大小为成本的边
这个时候的割有三种情况：
1.把收益割掉了，此时支出>收入
2.把支出割掉了，此时支出<收入
3.支出和收入同时割掉了，支出=收入
总的答案就是sum-割
|
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 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #include <queue> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') 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 E 400000 #define N 70050 struct Tedge { int from,to,cap,flow; }edge[E]; #define FROM edge[i].from #define TO edge[i].to #define FLO (edge[i].cap-edge[i].flow) int e_tot,fst[N],NXT[E]; int n,m,tot; void add_e(int _,int __,int ___) { edge[e_tot].from=_; edge[e_tot].to=__; edge[e_tot].cap=___; edge[e_tot].flow=0; NXT[e_tot]=fst[_]; fst[_]=e_tot++; edge[e_tot].from=__; edge[e_tot].to=_; edge[e_tot].cap=___; edge[e_tot].flow=___; NXT[e_tot]=fst[__]; fst[__]=e_tot++; } #define calc(x) (x+m) #define S 0 #define T N-1 void pre() { memset(fst,-1,sizeof(fst)); read(n); read(m); int _,__,___; for(int i=1;i<=n;i++) { read(_); add_e(calc(i),T,_); } for(int i=1;i<=m;i++) { read(_); read(__); read(___); add_e(S,i,___); tot+=___; add_e(i,calc(__),INF); add_e(i,calc(_),INF); } } int dist[N],p[N],cur[N],cnt[N]; int Augment() { int node,cur,i; cur=INF; node=T; while(node!=S) { i=p[node]; cur=min(cur,FLO); node=FROM; } node=T; while(node!=S) { i=p[node]; edge[i].flow+=cur; edge[i^1].flow-=cur; node=FROM; } return cur; } bool bfs() { int x; dist[T]=1; queue<int> Q; Q.push(T); while(!Q.empty()) { x=Q.front(); Q.pop(); for(int i=fst[x];~i;i=NXT[i]) if(!FLO&&!dist[TO]) { Q.push(TO); dist[TO]=dist[x]+1; } } return dist[S]!=0; } int ISAP() { int node=S,ret=0; bool flag; if(!bfs()) return false; for(int i=0;i<N;i++) { cur[i]=fst[i]; if(dist[i]) cnt[dist[i]]++; } while(dist[S]<=n*2+2) { if(node==T) { ret+=Augment(); node=S; } flag=false; for(int i=cur[node];~i;i=NXT[i]) if(dist[TO]==dist[node]-1&&FLO) { p[TO]=cur[node]=i; node=TO; flag=true; break; } if(flag) continue; int M=N-1; cur[node]=fst[node]; for(int i=fst[node];~i;i=NXT[i]) { if(!FLO) continue; M=min(M,dist[TO]+1); } if(!--cnt[dist[node]]) break; cnt[dist[node]=M]++; if(node!=S) node=edge[p[node]].from; } return ret; } int main() { pre(); printf("%d\n",tot-ISAP()); return 0; } |