題目鏈接：點(diǎn)擊查看

題目大意：Dumbulidone和Euphemia玩一個(gè)挑卡片游戲.
Dumbulidone會(huì)給出N對(duì)信封，每個(gè)信封里有兩張不同顏色的卡片，她會(huì)讓Euphemia從中挑選任意個(gè)信封，但是一對(duì)信封中最多只能挑選一個(gè)，（信封是透明的，可以看到里面卡片顏色）。等Euphemia挑好后，Dumbulidone會(huì)嘗試從Euphemia挑出的信封中再選出若干個(gè)（不可以不取），把其中的卡片取出，若存在一種方案使得取出的卡片中，每種顏色的卡片都有偶數(shù)張，那么Dumbulidone就贏了。Euphemia想知道在自己贏的前提下，她最多能選出多少信封。

輸入格式：

第一行一個(gè)整數(shù)N。
接下來N行，每行4個(gè)整數(shù)，描述一對(duì)信封中卡片顏色，前兩個(gè)是一個(gè)信封中的，后兩個(gè)是一個(gè)信封中的。

?

輸出格式：

一個(gè)整數(shù)，表示答案。

?

樣例輸入：

樣例輸入一 4 0 1 0 5 5 1 0 5 1 2 0 1 1 5 2 0 樣例輸入二 6 1 4 1 4 2 4 2 4 0 3 0 3 0 4 0 4 4 3 4 3 1 3 1 3

?

樣例輸出：

樣例輸出一 3 樣例輸出二 4

?

數(shù)據(jù)范圍：

對(duì)于30%的數(shù)據(jù)滿足N<=10
對(duì)于100%的數(shù)據(jù)滿足N<=300,所有數(shù)<=10^7.

?

時(shí)間限制：

1S

?

空間限制：

256M

題目分析：感覺挺好的一道題目，斷斷續(xù)續(xù)想了三天差不多想明白了該怎么做，首先題目的意思比較抽象，我們需要轉(zhuǎn)換一下，可以將顏色視為點(diǎn)，信封視為邊，問題就轉(zhuǎn)換為了，最多可以選擇多少條邊，使得組成的圖中不存在環(huán)，因?yàn)榍懊娴倪x擇會(huì)影響到全局的結(jié)果，所以不能用dp轉(zhuǎn)移狀態(tài)，在圖論中可以尋找增廣路來使得答案最優(yōu)，每次不斷嘗試尋找增廣路更新答案就好了，因?yàn)閿?shù)據(jù)比較小，我們可以直接枚舉每條邊，嘗試加入到圖中，如果可以直接加入的話，也就是加入某條邊后圖中仍然無環(huán)，那么這條邊就可以直接加入，相反如果加入后會(huì)出現(xiàn)環(huán)，那么需要尋找增廣路，這里尋找增廣路的方法和匈牙利算法的很像，也是類似于二分圖，這里二分圖的一個(gè)部分代表著已經(jīng)用過的邊，另一部分代表著沒有用過的邊，如果加入某條邊后會(huì)讓圖中出現(xiàn)環(huán)，那么顯然這條邊和環(huán)上的其他邊是不能同時(shí)存在于一個(gè)部分的，我們可以建邊，這里的建邊是對(duì)于信封建邊，也就是代表著這兩個(gè)信封不能同時(shí)選擇，對(duì)信封建好邊后，嘗試能否增廣就好了，可以增廣的條件是找到一條信封連成的路，使得第一個(gè)信封和最后一個(gè)信封都屬于二分圖中沒有用過的邊

最后就是因?yàn)轭伾容^多，但我們實(shí)際上用不到其絕對(duì)大小，所以離散化一下得到其相對(duì)大小，方便后續(xù)操作

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=610;vector<int>v; int f[N],n;struct Edge {int u,v,vis;Edge(){vis=0;} }Edge[N];void discreate()//離散化 {sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());for(int i=0;i<2*n;i++){Edge[i].u=lower_bound(v.begin(),v.end(),Edge[i].u)-v.begin();Edge[i].v=lower_bound(v.begin(),v.end(),Edge[i].v)-v.begin();} }int find(int x) {return f[x]==x?x:f[x]=find(f[x]); }bool merge(int x,int y) {int xx=find(x);int yy=find(y);if(xx!=yy){f[xx]=yy;return true;}return false; }struct Node {int to,id;Node(int to,int id):to(to),id(id){} };vector<Node>point[N<<1];//顏色連邊 vector<int>edge[N];//信封連邊 void init_point() {for(int i=0;i<v.size();i++)f[i]=i;for(int i=0;i<v.size();i++)point[i].clear(); }void build_point(int now)//建立點(diǎn)之間的聯(lián)系 { init_point();for(int i=0;i<now;i++)if(Edge[i].vis){int u=Edge[i].u;int v=Edge[i].v;point[u].push_back(Node(v,i));point[v].push_back(Node(u,i));merge(u,v);} }bool ok[N];//標(biāo)記哪條邊可以作為增廣路的終邊 int vis[N];bool dfs(int u,int fa,int id)//找環(huán) {if(u==fa)//有環(huán) return true;vis[u]=id;for(int i=0;i<point[u].size();i++){int v=point[u][i].to;if(vis[v]==id)continue;if(dfs(v,fa,id))//將環(huán)上的所有信封與id信封連邊 {edge[id].push_back(point[u][i].id);edge[point[u][i].id].push_back(id);return true;}}return false; }void init_edge(int now) {for(int i=0;i<=(now^1);i++)edge[i].clear();memset(ok,false,sizeof(ok));memset(vis,-1,sizeof(vis)); }void build_edge(int now)//建立信封之間的聯(lián)系 {init_edge(now);for(int i=0;i<=now;i++)edge[i].push_back(i^1);for(int i=0;i<=now;i++){if(!Edge[i].vis)//如果這條邊沒被用過{if(dfs(Edge[i].u,Edge[i].v,i))//加入后有環(huán)ok[i]=false;else//無環(huán) ok[i]=true; }} }bool dfs(int u) {vis[u]=true;for(int i=0;i<edge[u].size();i++){int v=edge[u][i];if(vis[v])continue;if((Edge[u].vis^Edge[v].vis)==1){if(ok[v]||dfs(v)){Edge[v].vis^=1;return true;}}}return false; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%d",&n);for(int i=0;i<2*n;i++){scanf("%d%d",&Edge[i].u,&Edge[i].v);v.push_back(Edge[i].u);v.push_back(Edge[i].v);}discreate();int ans=0;for(int i=0;i<2*n;i++)//遍歷每個(gè)信封 {build_point(i);//對(duì)于顏色建邊if(merge(Edge[i].u,Edge[i].v))//加入后無環(huán)，則直接加入 {Edge[i].vis=true;ans++;continue;}build_edge(i);//對(duì)于信封建邊memset(vis,false,sizeof(vis));if(dfs(i))//可以找到增廣路，則說明可以加入這條邊 {Edge[i].vis=true;ans++;}}printf("%d\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的XJOJ - 选信封(离散化+增广路)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。