通过颓了一个题解,终于也搞定了这个专题。
大神都颓题解。
——By skyh
无限之环
颓题解就行了。
建图是真的恶心。不很好想。
还是自己想到了一部分,就是看到题目里说“直线形不能转”就感觉要分类讨论。
无非就那么几类:空格,单个管,L型,直线型,T型,十字形
我一直以为这道题是最小割,然后我就死掉了,思维僵化,实际上这道题是费用流。
惯性拆点,每个点拆成5个,分别是原点以及四个方向。
而且还要染色,就是那种棋盘黑白染色。
根据水管最开始的方向,将原点与剩下的4个点连边。并且根据黑白颜色讲源汇与原点连边。(我是白连源黑连汇)
然后考虑旋转,分类讨论:
单个管:这个好说,讲原有方向分别向其它方向连边,对立方向费用为2其余费用为1。
L型:它有3种旋转,改变一个支管的方向费用为1,全都改变为2,所以关键就在于改变了几个管。
以上右为例,上向下连1费用边,右向左连1费用边,这样就做到了上述要求。(注意不能是上向左,下向右,考虑实际含义)
直线型:不能旋转,不连边
T型:和单个管差不多。
十字型:不用连。
这样的话,黑白染色之后跑流,如果流量==水管接头个数/2,那么就有解,就输出最小费用,否则0。
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 const int xx[]={-1,0,1,0},yy[]={0,1,0,-1}; 5 #define X i+xx[p] 6 #define Y j+yy[p] 7 #define S 1000005 8 #define k knd[i][j] 9 #define O o[i][j] 10 #define Q i+j&1^1 11 int l[S],to[S],v[S],w[S],fir[S],o[2002][2002][5],ec=1,pc,n,m,E,tot,knd[2005][2005],ans; 12 int d[S],pre[S],q[S],iq[S]; 13 void link(int a,int b,int V,int W){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;v[ec]=V;w[ec]=W;} 14 void con(int a,int b,int V,int W,int opt=0){if(opt)a^=b^=a^=b;link(a,b,V,W);link(b,a,0,-W);} 15 bool SPFA(){ 16 for(int i=1;i<=E;++i)d[i]=S; 17 for(int h=1,t=1;h<=t;iq[q[h]]=0,++h)for(int i=fir[q[h]];i;i=l[i])if(d[to[i]]>d[q[h]]+w[i]&&v[i]){ 18 d[to[i]]=d[q[h]]+w[i];pre[to[i]]=i; 19 if(!iq[to[i]])iq[q[++t]=to[i]]=1; 20 }return d[E]<S; 21 } 22 int main(){ 23 scanf("%d%d",&n,&m); 24 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)for(int p=0;p<=4;++p)o[i][j][p]=++pc; 25 E=++pc; 26 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(i+j&1)con(0,O[0],4,0);else con(O[0],E,4,0); 27 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)scanf("%d",&k); 28 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)for(int s=0;s<4;++s)if(k&1<<s)con(O[0],O[s+1],1,0,Q),tot++; 29 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){ 30 if(k== 1)con(O[1],O[2],1,1,Q),con(O[1],O[3],1,2,Q),con(O[1],O[4],1,1,Q); 31 if(k== 2)con(O[2],O[1],1,1,Q),con(O[2],O[3],1,1,Q),con(O[2],O[4],1,2,Q); 32 if(k== 4)con(O[3],O[2],1,1,Q),con(O[3],O[4],1,1,Q),con(O[3],O[1],1,2,Q); 33 if(k== 8)con(O[4],O[2],1,2,Q),con(O[4],O[3],1,1,Q),con(O[4],O[1],1,1,Q); 34 if(k== 3)con(O[2],O[4],1,1,Q),con(O[1],O[3],1,1,Q); 35 if(k== 6)con(O[3],O[1],1,1,Q),con(O[2],O[4],1,1,Q); 36 if(k==12)con(O[4],O[2],1,1,Q),con(O[3],O[1],1,1,Q); 37 if(k== 9)con(O[1],O[3],1,1,Q),con(O[4],O[2],1,1,Q); 38 if(k==14)con(O[2],O[1],1,1,Q),con(O[4],O[1],1,1,Q),con(O[3],O[1],1,2,Q); 39 if(k==13)con(O[3],O[2],1,1,Q),con(O[1],O[2],1,1,Q),con(O[4],O[2],1,2,Q); 40 if(k==11)con(O[2],O[3],1,1,Q),con(O[4],O[3],1,1,Q),con(O[1],O[3],1,2,Q); 41 if(k== 7)con(O[1],O[4],1,1,Q),con(O[3],O[4],1,1,Q),con(O[2],O[4],1,2,Q); 42 } 43 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)for(int p=0;p<4;++p)if(1<=X&&X<=n&&1<=Y&&Y<=m) 44 con(O[p+1],o[X][Y][(p^2)+1],1,0); 45 while(SPFA()){tot-=2;for(int i=pre[E];i;i=pre[to[i^1]])ans+=w[i],v[i]--,v[i^1]++;} 46 printf("%d\n",tot?-1:ans); 47 }代码感人
星际竞速
上下界无源汇最小费用可行流板子。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 #define E 2*n+1 5 #define S 2*n+2 6 #define Q 333333 7 int n,m,fir[Q],l[Q],to[Q],v[Q],w[Q],ec=1,C,q[Q],d[Q],iq[Q],pre[Q]; 8 void link(int a,int b,int V,int W){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;v[ec]=V;w[ec]=W;} 9 bool SPFA(){ 10 for(int i=1;i<=S;++i)d[i]=0x3fffffff; 11 for(int h=1,t=1;h<=t;iq[q[h]]=0,++h)for(int i=fir[q[h]];i;i=l[i])if(v[i]&&d[to[i]]>d[q[h]]+w[i]){ 12 d[to[i]]=d[q[h]]+w[i];pre[to[i]]=i; 13 if(!iq[to[i]])iq[q[++t]=to[i]]=1; 14 }return d[E]<0x3fffffff; 15 } 16 int main(){ 17 scanf("%d%d",&n,&m); 18 link(0,S,1,0);link(S,0,0,0); 19 for(int i=1,x;i<=n;++i)scanf("%d",&x), 20 link(S,i,1,x),link(i,S,0,-x),link(i+n,S,1,0),link(S,i+n,0,0), 21 link(i,E,1,0),link(E,i,0,0),link(0,i+n,1,0),link(i+n,0,0,0); 22 for(int i=1,a,b,c;i<=m;++i){ 23 scanf("%d%d%d",&a,&b,&c);if(a>b)a^=b^=a^=b; 24 link(a+n,b,1,c);link(b,a+n,0,-c); 25 } 26 while(SPFA())for(int i=pre[E];i;i=pre[to[i^1]])C+=w[i],v[i]--,v[i^1]++; 27 printf("%d\n",C); 28 }View Code
千钧一发
看起来很像《数字配对》?然后我又用鬼畜的联动边权解决了。
尝试,看那两个条件,想(很长)一段时间,就知道可以按照奇偶性分成二分图。
1 #include<cstdio> 2 #include<cmath> 3 #include<iostream> 4 using namespace std; 5 #define M 1000000000 6 #define E 2*n+1 7 int a[2005],b[2005],n,ec=3,ans,q[2005],d[2005],fir[2005],l[2000005],to[2000005],v[2000005]; 8 void link(int a,int b,int V){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;v[ec]=V;} 9 bool bfs(){ 10 for(int i=1;i<=E;++i)d[i]=0; 11 for(int h=1,t=1;h<=t;++h)for(int i=fir[q[h]];i;i=l[i])if(v[i]&&!d[to[i]]) 12 d[q[++t]=to[i]]=d[q[h]]+1; 13 return d[E]; 14 } 15 int dfs(int p,int flow){ 16 if(p==E)return flow;int r=flow; 17 for(int i=fir[p];i;i=l[i])if(v[i]&&d[to[i]]==d[p]+1&&r){ 18 int x=dfs(to[i],min(v[i],r)); 19 if(!x)d[to[i]]=0; 20 v[i]-=x;v[i^1]+=x,v[i^2]-=x;v[i^3]+=x;r-=x; 21 }return flow-r; 22 } 23 bool ju(long long x){int p=sqrt(x);return 1ll*p*p==x;} 24 int gcd(int a,int b){return b?gcd(b,a%b):a;} 25 int main(){ 26 scanf("%d",&n);d[0]=1; 27 for(int i=1;i<=n;++i)scanf("%d",&a[i]); 28 for(int i=1;i<=n;++i)scanf("%d",&b[i]),ans+=b[i]; 29 for(int i=1;i<=n;++i)link(0,i,b[i]),link(i,0,0),link(n+i,E,b[i]),link(E,n+i,0); 30 for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)if(ju(1ll*a[i]*a[i]+1ll*a[j]*a[j])&&gcd(a[i],a[j])==1) 31 link(i,j+n,M),link(j+n,i,0),link(j,i+n,M),link(i+n,j,0); 32 while(bfs())ans-=dfs(0,M);printf("%d\n",ans); 33 }View Code
老C的方块
LNC大喊标签被我听到了,然后稍微想一下就会了。
观察,只有竖线没有横线,也许可用?
再发现,他讨厌的图形都被竖线劈成两半,左右都是2个方块。
再发现,其实就是左边距离为2,1,右边距离为1,2的4个点构成一个讨厌的图形。
最小割。四色染色。
这样编号后,所有讨厌的图形都可以表示为ABCD。然后建四分图就好了。
1 #include<cstdio> 2 #include<map> 3 using namespace std; 4 map<pair<int,int>,int>M; 5 const int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; 6 #define tx X[i]+dx[j] 7 #define ty Y[i]+dy[j] 8 #define inf 0x3fffffff 9 #define S 13333333 10 int r,c,n,X[S],Y[S],C[S],ans,fir[S],l[S],to[S],v[S],ec=1,d[S],q[S]; 11 int knd(int x,int y){return x&1?y&3:1000005-y&3;} 12 void link(int a,int b,int V){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;v[ec]=V;} 13 void con(int a,int b,int V){link(a,b,V);link(b,a,0);} 14 bool bfs(){ 15 for(int i=1;i<=(n<<1|1);++i)d[i]=0; 16 for(int h=1,t=1;h<=t;++h)for(int i=fir[q[h]];i;i=l[i])if(v[i]&&!d[to[i]]) 17 d[q[++t]=to[i]]=d[q[h]]+1; 18 return d[1]; 19 } 20 int dfs(int p,int flow){ 21 int r=flow;if(p==1)return r; 22 for(int i=fir[p];i&&r;i=l[i])if(v[i]&&d[to[i]]==d[p]+1){ 23 int x=dfs(to[i],min(v[i],r)); 24 if(!x)d[to[i]]=0; 25 v[i]-=x;v[i^1]+=x;r-=x; 26 }return flow-r; 27 } 28 int main(){ 29 scanf("%d%d%d",&r,&c,&n);d[0]=1; 30 for(int i=1;i<=n;++i)scanf("%d%d%d",&Y[i],&X[i],&C[i]),M[make_pair(X[i],Y[i])]=i; 31 for(int i=1;i<=n;++i)con(i<<1,i<<1|1,C[i]); 32 for(int i=1;i<=n;++i)if(!knd(X[i],Y[i]))con(0,i<<1,inf); 33 else for(int j=0;j<4;++j)if(M[make_pair(tx,ty)]&&knd(tx,ty)==knd(X[i],Y[i])-1)con(M[make_pair(tx,ty)]<<1|1,i<<1,inf); 34 for(int i=1;i<=n;++i)if(knd(X[i],Y[i])==3)con(i<<1|1,1,inf); 35 while(bfs())ans+=dfs(0,inf);printf("%d\n",ans); 36 }View Code
线性代数
解出来,发现式子的含义就是$\sum\limits A_i \times A_j \times B_{i,j} - \sum\limits C_i \times A_i$
选一个数付出C代价,同时选得到B收益。
暴力。
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 #define M 40000000 5 int n,fir[255555],l[1555555],to[1555555],v[1555555],q[1555555],d[1555555],E,pc,ec=1; 6 int B[555][555],C[555],ans; 7 void link(int a,int b,int V){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;v[ec]=V;} 8 void con(int a,int b,int V){link(a,b,V);link(b,a,V);} 9 bool bfs(){ 10 for(int i=1;i<=E;++i)d[i]=0; 11 for(int h=1,t=1;h<=t;++h)for(int i=fir[q[h]];i;i=l[i])if(v[i]&&!d[to[i]]) 12 d[q[++t]=to[i]]=d[q[h]]+1; 13 return d[E]; 14 } 15 int dfs(int p,int flow){ 16 int r=flow;if(p==E)return flow; 17 for(int i=fir[p];i&&r;i=l[i])if(v[i]&&d[to[i]]==d[p]+1){ 18 int x=dfs(to[i],min(v[i],r)); 19 if(!x)d[to[i]]=0; 20 v[i]-=x;v[i^1]+=1;r-=x; 21 }return flow-r; 22 } 23 int main(){ 24 scanf("%d",&n);pc=n;E=n*n+n+1; 25 for(int i=1;i<=n;++i)for(int j=1,x;j<=n;++j)scanf("%d",&B[i][j]),ans+=B[i][j]; 26 for(int i=1,x;i<=n;++i)scanf("%d",&x),con(0,i,x); 27 for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)link(i,++pc,M),link(j,pc,M),link(pc,E,B[i][j]); 28 while(bfs())ans-=dfs(0,M);printf("%d\n",ans); 29 }View Code
优化建边。
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 #define M 40000000 5 #define E n+1 6 int n,fir[255555],l[1555555],to[1555555],v[1555555],q[1555555],d[1555555],ec=1; 7 int B[555][555],C[555],ans,b[555]; 8 void link(int a,int b,int V){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;v[ec]=V;} 9 void con(int a,int b,int V){link(a,b,V);link(b,a,V);} 10 bool bfs(){ 11 for(int i=1;i<=E;++i)d[i]=0; 12 for(int h=1,t=1;h<=t;++h)for(int i=fir[q[h]];i;i=l[i])if(v[i]&&!d[to[i]]) 13 d[q[++t]=to[i]]=d[q[h]]+1; 14 return d[E]; 15 } 16 int dfs(int p,int flow){ 17 int r=flow;if(p==E)return flow; 18 for(int i=fir[p];i&&r;i=l[i])if(v[i]&&d[to[i]]==d[p]+1){ 19 int x=dfs(to[i],min(v[i],r)); 20 if(!x)d[to[i]]=0; 21 v[i]-=x;v[i^1]+=1;r-=x; 22 }return flow-r; 23 } 24 int main(){ 25 scanf("%d",&n); 26 for(int i=1;i<=n;++i)for(int j=1,x;j<=n;++j)scanf("%d",&B[i][j]),ans+=B[i][j],b[i]+=B[i][j]; 27 for(int i=1,x;i<=n;++i)scanf("%d",&x),con(0,i,x),con(i,E,b[i]); 28 for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)con(i,j,B[i][j]); 29 while(bfs())ans-=dfs(0,M);printf("%d\n",ans); 30 }View Code