程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> zoj 3760 Treasure Hunting 最大獨立集

zoj 3760 Treasure Hunting 最大獨立集

編輯：C++入門知識

首先根據x^y的奇偶將圖分成X，Y集合，然後若對任意 x,y ，不滿足gcd的條件，既連邊，求最大獨立集即可 【最大獨立集=總權值-最小點覆蓋(最大流，最小割)】。

為什麼可以這樣分成二分圖，因為奇數和奇數，或者偶數和偶數異或的時候，二進制第一位一定是0，也就是一定是偶數，題目告訴了我們P一定是偶數，所以它們和P一定至少有一個公約數2，所以它們一定沒有邊（我們是以不滿足條件建邊的）。

最大獨立集的概念就是，選出權值最大的點，使他們兩兩都沒有邊相連。

具體的建圖代碼就是常規的二分圖。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps  1e-12
#define INF   0x7fffffff
#define maxn 4222
using namespace std;
int n,m;
int en;
int st,ed;	//源點和匯點
int dis[maxn] ;//dis[i],表示  到 原點  s 的 層數
int que[999999];
struct edge
{
	int to,c,next;
};
edge e[999999];
int head[maxn];
void add(int a,int b,int c)
{
	e[en].to=b;
	e[en].c=c;
	e[en].next=head[a];
	head[a]=en++;
	e[en].to=a;
	e[en].c=0;
	e[en].next=head[b];
	head[b]=en++;
}
int bfs()
{
    memset(dis,-1,sizeof(dis));
    dis[st]=0;
    int front=0,rear=0;
    que[rear++]=st;
    while(front
  1. 上一頁:
  2. 下一頁:
C++入門知識
[hdu-2044] 一只小蜜蜂

一只小蜜蜂... Time Limit: 200
scala入門-09 scala高階函數

scala入門-09 scala高階函數 我們做spar
OpenCV+海康威視攝像頭的實時讀取

OpenCV+海康威視攝像頭的實時讀取 OpenCV+海康威
HDU 2955 Robberies（dp）

HDU 2955 Robberies（dp） Prob
TCP、UDP、RTP(RTCP)異同與區別，rtprtcp

TCP、UDP、RTP(RTCP)異同與區別，rtprtcp
C++ 關鍵字淺談，關鍵字淺談

C++ 關鍵字淺談，關鍵字淺談　　這裡有一個游戲：要求寫一個
相關文章
閱讀排行榜
C++ 預處理器 C++ 虛函數與純虛函數，函數 新手入門：C/C++中枚舉類型(enum) Accelerated C++ 學習筆記及題解----第零章 Codeforces Round #137 (Div. 2) UVA - 1356 Bridge poj 1222 EXTENDED LIGHTS OUT（高斯消元） POJ 3126 Prime Path( 廣搜 ) 遍歷所有進程並找到指定進程停止 [LeetCode]Largest Number ZOJ 3772 Calculate the Function (線段樹 + 矩陣)
熱門圖文
高級技術學者對C++代碼進行編制 最大堆排序 Ubuntu11.04 安裝後要做的20件事情 PHP獲取毫秒級時間戳 spring mvc-maven+springmvc 報錯，找了一下午沒解決。哪位大神幫忙看看。 php去除HTML標簽實例 C#銳利體驗之第八講 索引器與操作符重載 C語言學習教程第七章-結構與聯合(5)
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved