首页 > 代码库 > poj3020(Antenna Placement)
poj3020(Antenna Placement)
题目地址：Antenna Placement
题目大意：
给你一个图里面包含“o”和“*”，*表示需要天线覆盖的区域，已知天线每次最多可以覆盖相邻的两哥*。问最少需要几个*。
解题思路：
利用二分匹配，这里不是一个集合向另一个集合的定点建图，而是由一个*点的位置向四周有*的位置建图。因为一般的二分匹配是单向边，而这个图建的是双向边
所以找到的最大匹配需要除以2.
最少需要天线的个数： 最大匹配数/2+未匹配数 而未匹配数＝*的总数－匹配数/2×2＝*的总数－匹配数 所以答案是*的总数－最大匹配数/2。
代码：
1 /*两个代码：一个是输入建图匹配的时候上下左右寻找。一个是先利用*的上下左右建图。*/ 2 #include <algorithm> 3 #include <iostream> 4 #include <sstream> 5 #include <cstdlib> 6 #include <cstring> 7 #include <cstdio> 8 #include <string> 9 #include <bitset> 10 #include <vector> 11 #include <queue> 12 #include <stack> 13 #include <cmath> 14 #include <list> 15 //#include <map> 16 #include <set> 17 using namespace std; 18 /***************************************/ 19 #define ll long long 20 #define int64 __int64 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {-1,1,0,0}; 26 const int d1y[]= {0,0,-1,1}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 /***************************************/ 32 void openfile() 33 { 34 freopen("data.in","rb",stdin); 35 freopen("data.out","wb",stdout); 36 } 37 /**********************华丽丽的分割线,以上为模板部分*****************/ 38 #define MAXN 505 39 int nx,ny; 40 int G[MAXN][MAXN]; 41 int cx[MAXN][MAXN],cy[MAXN][MAXN]; 42 int vis[MAXN][MAXN]; 43 int path(int x1,int y1) 44 { 45 int i; 46 int x,y; 47 for(i=0; i<4; i++) 48 { 49 x=x1+d1x[i]; 50 y=y1+d1y[i]; 51 if (G[x][y]&&!vis[x][y]) 52 { 53 vis[x][y]=-1; 54 if (cy[x][y]==-1||path(cx[x][y],cy[x][y])) 55 { 56 cx[x][y]=x1; 57 cy[x][y]=y1; 58 return 1; 59 } 60 } 61 } 62 return 0; 63 } 64 int MaxMatch() 65 { 66 int cnt=0; 67 memset(cx,-1,sizeof(cx)); 68 memset(cy,-1,sizeof(cy)); 69 int i,j; 70 for(i=0; i<nx; i++) 71 for(j=0; j<ny; j++) 72 { 73 memset(vis,0,sizeof(vis)); 74 if (G[i][j]==1) 75 cnt+=path(i,j); 76 } 77 return cnt; 78 } 79 int main() 80 { 81 int cas; 82 scanf("%d",&cas); 83 while(cas--) 84 { 85 // int m; 86 scanf("%d%d",&nx,&ny); 87 int i,j; 88 int x,y; 89 int min=0; 90 int sum=0; 91 char c; 92 memset(G,0,sizeof(G)); 93 getchar(); 94 for(i=0; i<nx; i++) 95 { 96 for(j=0; j<ny; j++) 97 { 98 scanf("%c",&c); 99 if (c==‘*‘)100 {101 G[i][j]=1;102 sum++;103 }104 }105 getchar();106 }107 min+=MaxMatch();108 min=sum-min/2;109 printf("%d\n",min);110 }111 return 0;112 }113 /*********************************************/114 #include <algorithm>115 #include <iostream>116 #include <sstream>117 #include <cstdlib>118 #include <cstring>119 #include <cstdio>120 #include <string>121 #include <bitset>122 #include <vector>123 #include <queue>124 #include <stack>125 #include <cmath>126 #include <list>127 #include <map>128 #include <set>129 using namespace std;130 /***************************************/131 typedef vector<int> VI;132 typedef vector<char> VC;133 typedef vector<string> VS;134 typedef set<int> SI;135 typedef set<string> SS;136 typedef map<int ,int> MII;137 typedef map<string,int> MSI;138 typedef pair<int,int> PII;139 typedef vector<PII> VII;140 typedef vector<VI > VVI;141 /***************************************/142 #define clr(a,b) memset(a,b,sizeof(a))143 #define all(x) (x).begin(), (x).end()144 #define sz(x) ((int)(x).size())145 #define ll long long146 #define int64 __int64147 #define pb push_back148 #define mp make_pair149 #define LL(x) ((x)<<1)150 #define RR(x) ((x)<<1|1)151 #define ri(x) scanf("%d",&x)152 #define rii(x,y) scanf("%d%d",&x,&y)153 #define rd(x) scanf("%lf",&x)154 #define rdd(x,y) scanf("%lf%lf",&x,&y)155 #define rs(x) scanf("%s",x)156 #define pi(x) printf("%d",x)157 #define pin(x) printf("%d\n",x)158 #define ps(x) printf("%s",x)159 #define pn() printf("\n")160 #define sqr(x) ((x)*(x))161 #define rep(i,a,b) for(int i=(a);i<(b);i++)162 #define repu(i,a,b) for(int i=(a);i<=(b);i++)163 #define repd(i,a,b) for(int i=(a);i>=(b);i--)164 #define repc(i,a,c) for(int i=(a);(c);i++)165 /***************************************/166 const int INF = 0x7f7f7f7f;167 const double eps = 1e-8;168 const double PIE=acos(-1.0);169 const int dx[]= {0,1,0,-1};170 const int dy[]= {1,0,-1,0};171 const int fx[]= {-1,-1,-1,0,0,1,1,1};172 const int fy[]= {-1,0,1,-1,1,-1,0,1};173 /***************************************/174 void openfile()175 {176 freopen("data.in","rb",stdin);177 freopen("data.out","wb",stdout);178 }179 /**********************The End OF The Template*****************/180 181 const int N = 410;182 char edge[45][15];183 int h,w;184 vector<int>graph[N];185 int mx[N],my[N],vis[N];186 187 void init()188 {189 rep(i,0,N)190 graph[i].clear();191 clr(mx,-1);192 clr(my,-1);193 }194 195 int dfs(int u)196 {197 rep(i,0,(int)graph[u].size())198 {199 int v=graph[u][i];200 if(!vis[v])201 {202 vis[v]=1;203 if(my[v]==-1||dfs(my[v]))204 {205 my[v]=u;206 mx[u]=v;207 return 1;208 }209 }210 }211 return 0;212 }213 214 int hungray()215 {216 int cnt=0;217 rep(i,0,w*h)218 {219 if(mx[i]==-1)220 {221 clr(vis,0);222 if(dfs(i)) cnt++;223 }224 }225 return cnt;226 }227 228 int main()229 {230 int T;231 ri(T);232 while(T--)233 {234 init();235 rii(h,w);236 rep(i,0,h)237 rs(edge[i]);238 int ans=0;239 rep(i,0,h)240 {241 rep(j,0,w)242 {243 if(edge[i][j]==‘*‘)244 {245 ans++;246 int x=i*w+j;247 rep(k,0,4)248 {249 int newx=i+dx[k];250 int newy=j+dy[k];251 if(newx>=0&&newx<h&&newy>=0&&newy<w&&edge[newx][newy]==‘*‘)252 {253 int y=newx*w+newy;254 graph[x].push_back(y);255 }256 }257 }258 }259 }260 //pin(hungray()/2);261 printf("%d\n",ans-hungray()/2);262 }263 return 0;264 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。