很經典的網絡流問題. 對每個柱子拆點限制流量，所以拆點，每個柱子的入點向出點連一條容量為自身高度的邊 然后能跳出去的柱子向匯點連一條容量為inf的邊 能互相跳的柱子的出點向另一個柱子的入點連一條容量為inf（或者柱子的高度，已經限制過流量了）的邊 然后有蜥蜴的柱子從源點引一條容量為1的邊 直接跑isap，因為一點小錯調了好久.
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<queue>#include<algorithm>using namespace std;const int N=1000,inf=0x3f3f3f3f;int len[30][30],cur[N],head[N],p[N],dis[N],num[N],pic[30][30],stone[30][30];char ch[30];int n,m,d,r,s,t,c,sz,te,tot;queue<int>q;struct xiyi{ int x,y;}xy[400];struct edge{ int u,v,cap,flow,next;}e[100010]; int zs(int a,int b){return a>b?(a-b):(b-a);}void add(int u,int v,int cap){ e[++te].u=u; e[te].v=v; e[te].flow=0; e[te].cap=cap; e[te].next=head[u]; head[u]=te;}void insert(int u,int v,int cap){add(u,v,cap),add(v,u,0);}void bfs(){ memset(dis,0,sizeof(dis)); while(!q.empty())q.pop(); q.push(t); while(!q.empty()) { int v=q.front(); for (int i=head[v];i;i=e[i].next) { int u=e[i].v; if (e[i].cap==0&&!dis[u]) { dis[u]=dis[v]+1; q.push(u); } } q.pop(); }}int augment(){ int a=inf,x=t; while(x!=s) { a=min(e[p[x]].cap-e[p[x]].flow,a); x=e[p[x]].u; } x=t; while(x!=s) { e[p[x]].flow+=a; e[p[x]^1].flow-=a; x=e[p[x]].u; } return a;}int isap(){ int flow=0,x=s; copy(head,head+n+1,cur); memset(num,0,sizeof(num)); bfs(); for (int i=1;i<=n;++i) ++num[dis[i]]; while(dis[s]<n) { if (x==t) { flow+=augment(); x=s; } int ok=0; for (int i=head[x];i;i=e[i].next) { int v=e[i].v; if (e[i].cap>e[i].flow&&dis[v]+1==dis[x]) { p[v]=i; cur[x]=i; x=v; ok=1; break; } } if (!ok) { if (--num[dis[x]]==0)break; int mx=n-1; for (int i=head[x];i;i=e[i].next) { int v=e[i].v; if (e[i].cap>e[i].flow) mx=min(mx,dis[v]); } ++num[dis[x]=mx+1]; cur[x]=head[x]; if (x!=s)x=e[p[x]].u; } } return flow;}int main(){ sz=tot=0,te=1; memset(stone,0,sizeof(stone)); for (int i=0;i<=20;++i) { for (int j=0;j<=20;++j) len[i][j]=ceil(sqrt(i*i+j*j)); } cin>>r>>c>>d; for (int i=1;i<=r;++i) { scanf("%s",ch+1); for (int j=1;j<=c;++j) { pic[i][j]=ch[j]-'0'; if (pic[i][j])stone[i][j]=++sz,insert(sz,sz+1,pic[i][j]),++sz;//拆點連邊 } }// for (int i=1;i<=r;i++)// {// for (int j=1;j<=c;j++)// cout<<stone[i][j]<<' ';// cout<<endl;// } n=sz+2;s=sz+1,t=n; for (int i=1;i<=r;++i) { for (int j=1;j<=c;++j) if (pic[i][j]) { int mx=min(r,i+d),my=min(c,j+d); if (i<=d||j<=d||i+d>r||j+d>c)insert(stone[i][j]+1,t,pic[i][j]);//能跳出的邊向源點連邊 for (int x=max(i-d,1);x<=mx;++x) { for (int y=max(j-d,1);y<=my;++y) { if (pic[x][y]&&len[zs(x,i)][zs(y,j)]<=d&&(x!=i||y!=j))//能連通的石柱間連邊 insert(stone[i][j]+1,stone[x][y],inf); } } } } for (int i=1;i<=r;++i)//源點向蜥蜴連邊 { scanf("%s",ch+1); for (int j=1;j<=c;++j) { if (ch[j]=='L') ++tot,insert(s,stone[i][j],1); } }// for (int i=2;i<=te;i+=2)// cout<<e[i].u<<' '<<e[i].v<<' '<<e[i].cap<<endl; cout<<tot-isap()<<endl;}新聞熱點
疑難解答
