C题，这个数据按照题目要求是应该输出-1吗？ 但是试了一些ac同学的代码输出的结果出现了不一致的情况。

链接： https://ac.nowcoder.com/acm/problem/236773 思路： 首先针对每一个插座跑一遍匈牙利算法。 之后针对每一个插座，扩展两个点，其与其他电器的连接方式完全复制这个插座。 这样就可以模拟这个插排插在这个插座上的情况。 注意： 用邻接矩阵会超时。 代码： #include<iostream> #include<cstring> #include<bitset> using namespace std; const int N=1510,M=75510; int n,m,k; bitset<N>st; int...

枚举每一个点 针对第二个条件，缺哪些边，添哪些边就可以了 针对第三个条件，用最小路径点覆盖就可以了 #include<iostream> #include<cstring> using namespace std; int n,m; const int N=1e3; int g[N][N]; int st[N]; int match[N]; int find(int u,int x) { for(int i=1;i<=n;i++) { if(i==x) { continue; ...

将整个棋盘分为横坐标与纵坐标的和为奇数和偶数的两种，此时，棋盘就变为了一个二分图。 仅针对和为奇数的点而言，若这个点为′∗′'*'′∗′，如果它能匹配到邻近的也为′∗′'*'′∗′的点，那么cnt就加二。 cnt代表被能覆盖两个星星的牌。 而cnt_代表总的星星数。 那么最后的结果就是cnt/2+(cnt_-cnt) #include<iostream> #include<cstring> #include<vector> using namespace std; typedef pair<int,int>PII; vector<PII&g...

将每个点定义为二分图中的一条边，此时每条边都需要被他的任意一个端点覆盖，就变成了最小点覆盖问题。 而最小点覆盖=最大匹配 套匈牙利算法模板就好啦 #include<iostream> #include<cstring> using namespace std; const int N=1e6+10; int st[N],match[N]; int g[1005][1005]; int n,k; bool find(int u) { for(int i=1;i<=n;i++) { if(st[i]) { continue; } if(g[u...