程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj1486(二分圖刪邊匹配)

poj1486(二分圖刪邊匹配)

編輯:C++入門知識

題意:給n(n<=26)張幻燈片,每張上面都有一個數字。給出所有幻燈片的位置和數字的位置,問哪些幻燈片上的數字可以確定。


解法:首先,如果給的合法的話,匈牙利算出來的一定是完全匹配的(也就是說,第一遍二分匹配算出來的一定是完全匹配)。然後再嘗試刪掉每一條完全匹配中的邊,如果刪掉後不能完全匹配,則說明這條邊是必須的,所以就確定了這個匹配並輸出。如果算出的完全匹配中沒有一個匹配是必須的,就輸出none好了。


代碼:

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-8
const double pi=acos(-1.0);
typedef long long LL;
const int Max=10100;
const int INF=1000000007;

int n;
struct rec
{
    int minx,miny,maxx,maxy;
} recs[30];
bool num[30][30];
bool used[30];
int match[30];
int match2[30];
struct point
{
    int x,y;
} points[30];
bool OK(const rec& re,const point& p)
{
    return (p.x>=re.minx&&p.x<=re.maxx&&p.y>=re.miny&&p.y<=re.maxy);
}
bool dfs(int k)
{
     for(int i=0;i

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved