图片网站的优化,哪个网站做视频赚钱,网站几个页面,石家庄现状题目
题目链接
题意
告诉了n名球员的交换关系#xff0c;你现在拥有k名球员#xff0c;你想要其他k名球员(有的在自己队里)。
输出一种交换方案。
题解
第一步、求闭包。
我们需要在原来的交换矩阵上跑可达闭包#xff0c;即G[i][j]G[i][j]的含义是jj是否能通过i你现在拥有k名球员你想要其他k名球员(有的在自己队里)。
输出一种交换方案。
题解
第一步、求闭包。
我们需要在原来的交换矩阵上跑可达闭包即G[i][j]G[i][j]G[i][j]的含义是jjj是否能通过i" role="presentation" style="position: relative;">iii的一些交换得到例如用iii交换a" role="presentation" style="position: relative;">aaa,再用aaa交换b" role="presentation" style="position: relative;">bbb,再用bbb来交换j" role="presentation" style="position: relative;">jjj。预处理闭包的时间复杂度是O(n3)O(n3)O(n^3)。
第二步、建立二分图。
先预处理出将同时存在与现在队伍里和目标队伍里的球员这类球员不将其加入二分图中去。二分图的左半边是只出现在现在队伍里的球员二分图的右边是只出现在目标队伍里的球员。凡是现在队伍的球员aaa能够换成目标队伍里的球员b" role="presentation" style="position: relative;">bbb的就在(a,b)(a,b)(a,b)之间链接一条边。然后跑一个二分图匹配。(a,b)(a,b)(a,b)匹配的含义就是可以把我队的aaa换成目标队伍里的b" role="presentation" style="position: relative;">bbb并且不影响其他任何球员的归属。
第三步、无解判定。
当且仅当我队伍中所有加入二分图的球员都匹配上了说明有解其他情况无解。
第四步、输出方案。 注意大写字母代表这个球员当前属于我队。 我们遍历二分图中所有的匹配(A,b)(A,b)(A,b)然后从原矩阵任意找一条从aaa到b" role="presentation" style="position: relative;">bbb的路径例如A−c−d−E−f−bA−c−d−E−f−bA -> c -> d -> E -> f -> b。 那么我们输出方案如下E−ff−bA−cc−dd−EE−ff−bA−cc−dd−EE -> f，f - > b，A -> c，c -> d，d -> E 然后再把b设置为我队把A设置为非我队。 这样输出方案保证了把 A 换成 b 的同时其他的球员的归属没有发生改变。输出方案的算法从后往前依次找到属于当前位置的节点并把后面的箭头依次输出即可。例如先找到了EEE输出E#x2212;gt;f#xFF0C;f#x2212;gt;b" role="presentation" style="position: relative;">E−f，f−bE−f，f−bE -> f，f - > b 又找到了AAA，输出A#x2212;gt;c#xFF0C;c#x2212;gt;d#xFF0C;d#x2212;gt;E" role="presentation" style="position: relative;">A−c，c−d，d−EA−c，c−d，d−EA -> c，c -> d，d -> E。
第五步、细节。
如何寻找从AAA到b" role="presentation" style="position: relative;">bbb的一条路径呢。 使用dfs方法但要注意经过的点打上标记vis[i] 1但是在返回的时候不要将标记取消在返回的时候不要将标记取消在返回的时候不要将标记取消重要的话说三遍因为我们只要找到一条路径就好了如果在返回过程中将标记取消的话时间复杂度会爆掉。
证明不取消标记可以找到一条路径。
如果通过某条路径走到vvv节点而未能从v" role="presentation" style="position: relative;">vvv节点走到目标点的话通过其他路径走到vvscript typemath/tex idMathJax-Element-40v/script点也不会走到目标点这是很显然的。因此只要被访问过的点而没有走到终点我们就无需再次访问了。
代码
#include string.h
#include vector
#include queue
#include iostream
#include cstdio
using namespace std;
typedef std::vectorint::iterator iterator_t;
struct Edge {int from, to;
};
#define max_nodes 307
std::vectorEdge edges;
std::vectorint G[700];
int num_nodes;
int num_edges;
int num_left, num_right;int match[700];
bool check[700];inline void insert(int lefti, int righti){G[lefti].push_back(edges.size());edges.push_back((Edge){lefti, num_left righti});G[num_left righti].push_back(edges.size());edges.push_back((Edge){num_left righti, lefti});
}bool dfs(int u){for(iterator_t i G[u].begin(); i ! G[u].end(); i){int v edges[*i].to;if(check[v]) continue;check[v] true;if((match[v] -1) || dfs(match[v])){match[u] v;match[v] u;return true;}}return false;
}int hungarian(void){int ans 0;memset(match, -1, sizeof(match));for(int i 0; i num_left; i){if(match[i] ! -1) continue;memset(check, 0, sizeof(bool) * num_nodes);if(dfs(i)) ans;}return ans;
}
int MG2[max_nodes][max_nodes];
int n,k;
int wanted[max_nodes];
int myteam[max_nodes];
int vis[max_nodes];
int vv[max_nodes];
typedef pairint,int pii;
vectorpii fans;
vectorint vG[max_nodes];
pii ps[max_nodes];
int pcnt 0;
int main(){scanf(%d%d,n,k);for(int i 0;i k;i){int tmp;scanf(%d,tmp);myteam[tmp] 1;}for(int i 0;i k;i){int tmp;scanf(%d,tmp);wanted[tmp] 1;}for(int i 1;i n;i)for(int j 1;j n;j){char c;scanf( %c,c);MG2[i][j] c 1;if(c 1) vG[i].push_back(j);}//floydfor(int k 1;k n;k)for(int i 1;i n;i)for(int j 1;j n;j)MG2[i][j] | MG2[i][k]MG2[k][j];int cnt k;for(int i 1;i n;i)if(myteam[i] wanted[i])vis[i] 1,cnt--;num_nodes 2*n;num_right num_left n;for(int i 1;i n;i)if(!vis[i] myteam[i])for(int j 1;j n;j)if(!vis[j] wanted[j] MG2[i][j]){insert(i-1,j-1);}int ans hungarian();if(ans ! cnt)return 0*puts(NO);int dfs2(int,int);for(int i 1;i n;i){if(wanted[i]){memset(vv,0,sizeof(vv));int from match[i-1n]1;int to i;if(myteam[to]) continue;vv[from] 1 ;dfs2(from,to);//vv[from] 0;myteam[from] 0;myteam[to] 1;}}puts(YES);printf(%d\n,fans.size());for(auto p : fans)printf(%d %d\n,p.first,p.second);return 0;
}
int dfs2(int s,int t){if(s t)return 1;for(auto i : vG[s]){if(!vv[i]){vv[i] 1;int r dfs2(i,t);//vv[i] 0;if(r){ps[pcnt] make_pair(s,i);if(myteam[s]){while(pcnt--)fans.push_back(ps[pcnt]);pcnt 0;}return 1;}}}return 0;
}
