程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj 1548 Robots 最小路徑匹配解法

poj 1548 Robots 最小路徑匹配解法

編輯：關於C++
//最小路徑覆蓋=N-最大匹配
#include
#include
#include
#include
using namespace std;
const int maxn = 30*30;
int line[maxn][maxn];
int vis[maxn];
int match[maxn];
int N;
int find(int start)
{
int i;
for(i=1;i<=N;i++)
{
if(line[start][i]&&!vis[i])
{
vis[i]=1;
if(match[i]==-1||find(match[i]))
{
match[i]=start;
return 1;
}
}
}
return 0;
}
void Match()
{
memset(match , -1 ,sizeof(match));
int ans = 0;
for(int i = 1; i <= N ;i++)
{
memset(vis,0,sizeof(vis));
if(find(i))
ans++;
}
printf("%d\n",N-ans);
}
struct node
{
int x,y;
}gar[maxn];
int main()
{
int a,b;
//freopen("in.txt","r",stdin);
while(scanf("%d%d", &a ,&b)&&(a != -1 && b != -1))
{
memset(line, 0 ,sizeof(line));
if(!a && !b)
{
printf("0\n");
continue;
}
N = 0;
while(a && b)
{
gar[++N].x = a;
gar[N].y = b;
scanf("%d %d",&a ,&b);
}
memset(line, 0 ,sizeof(line));
for(int i = 1;i <= N ; i++)
for(int j = i+1 ;j <= N ;j++)
{
if(gar[i].x <= gar[j].x && gar[i].y <= gar[j].y)
line[i][j] = 1;
else if(gar[i].x >= gar[j].x && gar[i].y >= gar[j].y)
line[j][i] = 1;
}
Match();
}
return 0;
}









































  1. 上一頁:
  2. 下一頁:
關於C++
UVa 2038

Strategic gameDescriptionBob e
BZOJ 3112 Zjoi2013 防守戰線 單純形

題目大意：單純形*2。。。 #include #i
LeetCode[Math]: Excel Sheet Column Title

Given a positive integer, ret
UVA 11722（概率＋幾何）

 ProblemSolution求概率方法就是lr
C++之友元函數和友元類

在介紹類和對象時，已經說過類具有封裝性，類中的私有成員一般只
leetcode筆記：Search Insert Position

一. 題目描述 Given a sorted array

相關文章
閱讀排行榜
C++BUILDER的文件操作 在應用程序中控制Word 97的運行 POJ2676 2918 Sudoku 暴搜 文件合並與分隔 通過端口獲取IDE硬盤ID KV300技術分析(有關硬盤鎖) 在名字空間中聲明類和成員函數 C#項目調用C++的DLL程序 數據結構與算法 Vdsp(bf561)中的浮點運算（1）：文檔的說法 三維視圖繪制與消隱技術
熱門圖文
整蠱QQ截圖 JAVA的序列化和持久化的區別與聯系，java序列化 數據庫 javaweb-javaweb讀取數據庫圖片的問題 android ui-一個app開發的過程究竟是怎樣的？用到了哪些軟件來開發？ Asp.NET 多層登陸實現代碼 Yii使用CForm類(Form builder)上傳文件 設計和輸出一個鑽石圖形 Java中的方法“實踐”，java中方法實踐
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved