做网站写代码怎么样,站长推荐跳转,三亚发布紧急通知,无锡网站 制作题目大概就是说一个n*m的地图#xff0c;地图上每一块是陆地或浅海域或深海域#xff0c;可以填充若干个浅海域使其变为陆地#xff0c;问能得到的最长的陆地海岸线是多少。 也是很有意思的一道题。 一开始想歪了#xff0c;想着#xff0c;不考虑海岸线重合的情况那海岸线…题目大概就是说一个n*m的地图地图上每一块是陆地或浅海域或深海域可以填充若干个浅海域使其变为陆地问能得到的最长的陆地海岸线是多少。 也是很有意思的一道题。 一开始想歪了想着不考虑海岸线重合的情况那海岸线长度就是所有非深海域的个数*4而每一块要嘛是陆地要嘛不是陆地如果浅海域不变成陆地那么花费4而对于重合情况花费是2那样似乎是经典的二者选其一的最小割模型最后的答案就是所有非深海域的个数*4-最小割。 不过那个经典的模型是二者选法不同有额外花费而这儿是二者同时是陆地有额外花费这个额外花费指的是重合花费2——入手点也是这儿—— 对地图黑白染色两色的点分别作X部Y部X部向其相邻的Y部点连容量2的边源点向X部是陆地的点连容量INF的边是浅海域的点连容量4的边是深海域的点连容量0的边Y部是陆地的点向汇点连容量INF的边是浅海域的点连容量4的边是深海域的点连容量0的边如此建容量网络计算最小割就是要求的最少的花费了画画图就知道了。 1 #includecstdio2 #includecstring3 #includequeue4 #includealgorithm5 using namespace std;6 #define INF (130)7 #define MAXN 25558 #define MAXM 2555*25559 10 struct Edge{11 int v,cap,flow,next;12 }edge[MAXM];13 int vs,vt,NE,NV;14 int head[MAXN];15 16 void addEdge(int u,int v,int cap){17 edge[NE].vv; edge[NE].capcap; edge[NE].flow0;18 edge[NE].nexthead[u]; head[u]NE;19 edge[NE].vu; edge[NE].cap0; edge[NE].flow0;20 edge[NE].nexthead[v]; head[v]NE;21 }22 23 int level[MAXN];24 int gap[MAXN];25 void bfs(){26 memset(level,-1,sizeof(level));27 memset(gap,0,sizeof(gap));28 level[vt]0;29 gap[level[vt]];30 queueint que;31 que.push(vt);32 while(!que.empty()){33 int uque.front(); que.pop();34 for(int ihead[u]; i!-1; iedge[i].next){35 int vedge[i].v;36 if(level[v]!-1) continue;37 level[v]level[u]1;38 gap[level[v]];39 que.push(v);40 }41 }42 }43 44 int pre[MAXN];45 int cur[MAXN];46 int ISAP(){47 bfs();48 memset(pre,-1,sizeof(pre));49 memcpy(cur,head,sizeof(head));50 int upre[vs]vs,flow0,augINF;51 gap[0]NV;52 while(level[vs]NV){53 bool flagfalse;54 for(int icur[u]; i!-1; iedge[i].next){55 int vedge[i].v;56 if(edge[i].cap!edge[i].flow level[u]level[v]1){57 flagtrue;58 pre[v]u;59 uv;60 //aug(aug-1?edge[i].cap:min(aug,edge[i].cap));61 augmin(aug,edge[i].cap-edge[i].flow);62 if(vvt){63 flowaug;64 for(upre[v]; v!vs; vu,upre[u]){65 edge[cur[u]].flowaug;66 edge[cur[u]^1].flow-aug;67 }68 //aug-1;69 augINF;70 }71 break;72 }73 }74 if(flag) continue;75 int minlevelNV;76 for(int ihead[u]; i!-1; iedge[i].next){77 int vedge[i].v;78 if(edge[i].cap!edge[i].flow level[v]minlevel){79 minlevellevel[v];80 cur[u]i;81 }82 }83 if(--gap[level[u]]0) break;84 level[u]minlevel1;85 gap[level[u]];86 upre[u];87 }88 return flow;89 }90 int dx[]{0,1};91 int dy[]{1,0};92 int main(){93 char map[55][55];94 int t,n,m;95 scanf(%d,t);96 for(int cse1; cset; cse){97 scanf(%d%d,n,m);98 int tot0;99 for(int i0; in; i){
100 for(int j0; jm; j){
101 scanf( %c,map[i][j]);
102 if(map[i][j]!D) tot;
103 }
104 }
105 tot2;
106 vsn*m; vtvs1; NVvt1; NE0;
107 memset(head,-1,sizeof(head));
108 for(int i0; in; i){
109 for(int j0; jm; j){
110 if(ij1){
111 if(map[i][j].) addEdge(vs,i*mj,INF);
112 else if(map[i][j]E) addEdge(vs,i*mj,4);
113 for(int k0; k2; k){
114 int nxidx[k],nyjdy[k];
115 if(nx0 || nxn || ny0 || nym) continue;
116 addEdge(i*mj,nx*mny,2);
117 }
118 }else{
119 if(map[i][j].) addEdge(i*mj,vt,INF);
120 else if(map[i][j]E) addEdge(i*mj,vt,4);
121 for(int k0; k2; k){
122 int nxidx[k],nyjdy[k];
123 if(nx0 || nxn || ny0 || nym) continue;
124 addEdge(nx*mny,i*mj,2);
125 }
126 }
127 }
128 }
129 printf(Case %d: %d\n,cse,tot-ISAP());
130 }
131 return 0;
132 } 转载于:https://www.cnblogs.com/WABoss/p/5356616.html
