服装印花图案设计网站,设计一个网站要多久,易营宝智能建站,北京工商局网站如何做股东变更http://www.lydsy.com/JudgeOnline/problem.php?id4808 题意#xff1a; 思路#xff1a; 这图中的两个马只能选一个#xff0c;二选一#xff0c;很像二分图吧#xff0c;对能互吃的两个棋子连线#xff0c;在所选的任意两个棋子中#xff0c;都不能互相有连线#x… http://www.lydsy.com/JudgeOnline/problem.php?id4808 题意 思路 这图中的两个马只能选一个二选一很像二分图吧对能互吃的两个棋子连线在所选的任意两个棋子中都不能互相有连线这不就是最大点独立集吗 最大独立集 顶点个数 - 最大匹配。记得把坏了的格子去掉。 1 #includeiostream2 #includecstdio3 #includecstring4 using namespace std;5 6 int n,m,tot;7 int mp[205][205], head[40005], mark[40005];8 bool vis[40005];9
10 struct node
11 {
12 int v,next;
13 }e[8*40005];
14
15 int dx[] {-2,-2,-1,-1,1,1,2,2};
16 int dy[] {1,-1,2,-2,2,-2,1,-1};
17
18 void addEdge(int u, int v)
19 {
20 e[tot].v v;
21 e[tot].next head[u];
22 head[u] tot;
23 }
24
25 bool match(int u)
26 {
27 for(int ihead[u];i!-1;ie[i].next)
28 {
29 int v e[i].v;
30 if(!vis[v])
31 {
32 vis[v] true;
33 if(mark[v]-1 || match(mark[v]))
34 {
35 mark[v] u;
36 return true;
37 }
38 }
39 }
40 return false;
41 }
42
43 int main()
44 {
45 //freopen(in.txt,r,stdin);
46 int num 0;
47 scanf(%d%d,n,m);
48 for(int i1;in;i)
49 for(int j1;jm;j)
50 {
51 scanf(%d,mp[i][j]);
52 if(mp[i][j]) num;
53 }
54 tot 0;
55 memset(head,-1,sizeof(head));
56 for(int i1;in;i)
57 for(int j1;jm;j)
58 {
59 if(!mp[i][j])
60 {
61 for(int k0;k8;k)
62 {
63 int x idx[k];
64 int y jdy[k];
65 if(x1 || xn || y1 || ym) continue;
66 if(mp[x][y]1) continue;
67 int p1 (i-1)*mj;
68 int p2 (x-1)*my;
69 addEdge(p1,p2);
70 }
71 }
72 }
73 int sum 0;
74 memset(mark,-1,sizeof(mark));
75 for(int i1;in*m;i)
76 {
77 memset(vis,false,sizeof(vis));
78 if(match(i)) sum;
79 }
80 printf(%d\n,n*m-num-sum/2);
81 return 0;
82 } 转载于:https://www.cnblogs.com/zyb993963526/p/7904002.html
