oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1089 跟 TIOJ 1253. 砲打皮皮 一模一樣的題目，可以轉成二分圖最小點覆蓋，然後用最大匹配的做法去做，詳細可以去看那篇的題解 #include <bits/stdc++.h> using namespace std; #define N 500 vector<int> X[N+5],Y[N+5]; int fX[N+5], fY[N+5]; bitset<N+5> walked; bool dfs(int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n,k;cin>>n>>k; for(int i=1;i<=n;++i)fX[i]=fY[i]=-1; while(k--){ int s,e;cin>>s>>e; X[s].push_back(e); Y[e].push_back(s); } int ans=0; for(int i=1;i<=n;i++){ walked.reset(); if(dfs(i))ans++; } cout<<ans; return 0; } bool dfs(int x){ for(auto i:X[x]){ if(walked[i])continue; walked[i]=1; if(fY[i]==-1||dfs(fY[i])){ fY[i]=x;fX[x]=i; return 1; } }...

題目連結: http://tioj.infor.org/problems/1253 本題可以轉化為二分圖最小點覆蓋，因為不妨考慮把每隻皮皮當作邊，連接著一個列跟欄(如下圖) 而我們要求的不就是找到最少的列或欄使得每隻皮皮都被炸掉，剛好就是找到最少的點覆蓋所有的邊，而且這樣轉還有一個好處就是他保證會是二分圖，所以我們要做的事就是找到最小點覆蓋。不過二分圖最小點覆蓋又該如何找呢？可以證明，其實二分圖最小點覆蓋的數量就等於二分圖最大匹配的數量，因此問題又被轉化成了二分圖最大匹配，二分圖最大匹配有很多種作法，一種是新增一個起點連接所有左半圖，並新增一個終點連接所有右半圖，把問題又轉成最大流的流量，所以可以用dinic或ford fulkerson之類的演算法寫掉。不過因為是二分圖，所以其實有好的找匹配數的方法，就對於某一個點如果其還未被匹配，則看他可不可以跟其他點匹配，如果與他相鄰的某個點已經被匹配過了，那就請他試試看可不可以換點，如此遞迴下去即可求得最大匹配數。 p.s 詳細證明可以看 演算法筆記 #include <bits/stdc++.h> using namespace std; #define N 1000 int cnt=1; int ans=0; bitset<N+5> visited; vector<int> X[N+5], Y[N+5]; int matchX[N+5], matchY[N+5]; inline void init(int); bool DFS(int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n,k; cin>>n>>k; while(n!=0||k!=0){ init(n); for(int i=0;i<k;i++){ int s,e; cin>>s>>e; ...

題目連結: http://tioj.infor.org/problems/1292 裸樹上最小點覆蓋。而樹上最小點覆蓋該如何做呢?，不妨考慮先DFS一遍取得整棵樹的構造，之後從葉子走上去(可直接用DFS序列倒著跑)，若自己及自己的爸爸都沒有被任何點覆蓋，則把自己的爸爸放到點覆蓋集，因為這樣可以保證把所有點都放進去，而且因為是放爸爸進去，所以可以拿到最小的點覆蓋集。 #include <bits/stdc++.h> using namespace std; #define N 10000 vector<int> tree[N+10]; int deep[N+10]; vector<int> arr; bitset<N+10> poped; void DFS(int,int,int); int n; int main(){ scanf("%d",&n); for(int i=0;i<n-1;i++){ int s,e; scanf("%d%d",&s,&e); tree[s].push_back(e); tree[e].push_back(s); } int cnt=0; DFS(1,-1,0); for(int i=arr.size()-1;i>0;i--){ int cc=arr[i]; int ff=arr[i-1]; if(deep[ff]>=deep[cc])continue; if(!poped[ff]&&!poped[cc]){ poped[ff]=1; poped[cc]=1; cnt++; } ...