POJ1274 The Perfect Stall(二分圖)

題意:

一些奶牛只有在特定的圍欄中才能產奶,要求合理安排使能產奶的奶牛數達到最大。

要點:

二分圖裸題,最近剛學了二分圖,看下面的參考博客,寫的比較好:

參考博客:匈牙利算法


15479500Seasonal1274Accepted520K16MSC++736B2016-05-07 20:26:59
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int map[300][300], used[300],girl[300];
int n, m;bool find(int x)
{int i;for (i = 1; i <= m; i++){if (map[x][i] && !used[i]){used[i] = 1;if (girl[i] == -1 || find(girl[i]))//女孩還沒人追或者追的人可以挪動{girl[i] = x;return true;}}}return false;
}int main()
{int i, num,temp;while (scanf("%d%d", &n, &m) != EOF){memset(map, 0, sizeof(map));memset(girl, -1, sizeof(girl));for (i = 1; i <= n; i++){scanf("%d", &num);while (num--){scanf("%d", &temp);map[i][temp] = 1;}}int num = 0;for (i = 1; i <= n; i++){memset(used, 0, sizeof(used));//每次都要重新賦值為0if (find(i))num++;}printf("%d\n", num);}return 0;
}


轉載于:https://www.cnblogs.com/seasonal/p/10343749.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/458586.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/458586.shtml
英文地址,請注明出處:http://en.pswp.cn/news/458586.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

藍牙HCI剖析(一)

來自&#xff1a;http://blog.csdn.net/xiaoxiaopengbo/article/details/51334257 一.HCI介紹 HCI提供了訪問bluetooth control的統一接口&#xff0c;通俗來講&#xff0c;就是定義了特定的格式來控制藍牙芯片來做相應的動作&#xff08;比如inquiry,connect,disconnect&#…

c語言題庫2

96. struct name1{ char str; short x; int num; } struct name2{ char str;0 1 2 3 int num; 4 5 6 7 short x; 8 9 10 11 } sizeof(struct name1)? sizeof(struct name2)? 8、12 97. 讀文件file1.txt的內容&#xff08;例如&#xff09;&#xff1a; 12 34 56 …

ASP.NET狀緩存Cache的應用-提高數據庫讀取速度

ASP.NET狀緩存Cache的應用-提高數據庫讀取速度 原文:ASP.NET狀緩存Cache的應用-提高數據庫讀取速度一、 Cache概述 既然緩存中的數據其實是來自數據庫的&#xff0c;那么緩存中的數據如何和數據庫進行同步呢&#xff1f;一般來說&#xff0c;緩存中應該存放改動不大或者對…

2016年學習Linux決心書(老男孩教育在線課程班第二期)

我經過這4-5個月的學習后&#xff0c;我一定要達到月薪20&#xff2b;&#xff0c;為了達到這個目標我要付出如下10大行動&#xff1a;1.提前預習上課內容2.上課認真聽講&#xff0c;做好上課筆記3.課后認真做總結&#xff0c;完善筆記5.反復做實驗&#xff0c;并寫實驗文檔6.學…

WPF XAML 從零開始認識XAML

來自&#xff1a;http://blog.csdn.net/aoshilang2249/article/details/44158403 剖析最簡單的XMAL代碼: [html] view plaincopy <Window x:Class"MyFirstApplication.MainWindow" xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentati…

c語言題庫3

143. 枚舉元素本身由系統定義了一個表示序號的數值&#xff0c;從0 開始順序定義為0&#xff0c;1&#xff0c;2…。如在weekday中&#xff0c;sun值為0&#xff0c;mon值為1&#xff0c; …,sat值為6。 main(){  enum weekday  {   sun,mon,tue,wed,thu,fri,sat  } a,b…

入門級----測試的執行、環境的搭建、每日構建、測試記錄和跟蹤、回歸測試、測試總結和報告...

測試用例的準備&#xff0c;都是為了執行測試準備的。 測試環境的搭建 &#xff08;1&#xff09;測試數據&#xff1a;有些測試需要使用大批量的數據&#xff0c;例如容量測試、壓力測試等。根據產品的具體測試要求&#xff0c;可能需要在數據庫表插入大量的數據&#xff0c;準…

MFC讀取配置文件GetPrivateProfileString

VC中 3 個主要 寫入/讀取配置文件ini的函數&#xff1a;bool WritePrivateProfileString(LPCTSTR lpAppName,LPCTSTR lpKeyName,LPCTSTR lpString,LPCTSTR lpFileName);寫入.ini文件&#xff1b;DWORDGetPrivateProfileString(LPCTSTR lpAppName,LPCTSTR lpKeyName,LPCTSTR lpD…

UESTC 250 windy數 數位dp

題目鏈接 1 #include<bits/stdc.h>2 using namespace std;3 #define mem1(a) memset(a, -1, sizeof(a))4 #define ll long long5 int dp[20][20], digit[20], len;6 ll dfs(int len, int pre, bool fp, bool first) { //first表示前面的數是否全部為0&#xff0c; pr…

c語言面試題大全

C語言面試題大匯總 4. static有什么用途&#xff1f;&#xff08;請至少說明兩種&#xff09; 1.限制變量的作用域(DL:使其只在定義的當前文件中起作用&#xff0c;static是只能由與變量在同一個文件中定義的程序存取的全局變量。也就是說使全局變量成為文件的私有變量&#…

WindowsAPI詳解——GetCurrentDirectory 獲得程序當前目錄

每個Windows程序都有一個自己的當前目錄&#xff0c;默認是程序exe文件所在的目錄。系統在給程序加載動態鏈接庫文件(DLL)時先在程序當前目錄里查找要加載的DLL&#xff0c;如果在此目錄下沒有找到系統便會去Windows目錄下查找。在這兒我們主要將如何獲得程序的當前目錄&#x…

20151210小問題2

1、各瀏覽器下 scrollTop的差異 IE6/7/8&#xff1a; 對于沒有doctype聲明的頁面里可以使用 document.body.scrollTop 來獲取 scrollTop高度 &#xff1b; 對于有doctype聲明的頁面則可以使用 document.documentElement.scrollTop&#xff1b; Safari: safari 比較特別&#x…

限制MySQL Binlog的傳輸速率

最近一臺核心庫備庫完成恢復后打開slave&#xff0c;導致主庫傳送binlog&#xff0c;瞬間占滿網絡&#xff0c;觸發故障。 為了做一些限制&#xff0c; 給mysql在發送binlog的函數(mysql_binlog_send)里每隔一段時間sleep一次&#xff0c; 增加了兩個參數&#xff1a; master_s…

sprintf用法詳解

printf可能是許多程序員在開始學習C語言時接觸到的第二個函數&#xff08;我猜第一個是main&#xff09;&#xff0c;說起來&#xff0c;自然是老朋友了&#xff0c;可是&#xff0c;你對這個老朋友了解多嗎&#xff1f;你對它的那個孿生兄弟sprintf了解多嗎&#xff1f;在將各…

掌握 Ajax,第 2 部分: 使用 JavaScript 和 Ajax 發出異步請求

轉http://www.ibm.com/developerworks/cn/xml/wa-ajaxintro2/ 掌握 Ajax&#xff0c;第 2 部分: 使用 JavaScript 和 Ajax 發出異步請求 在 Web 請求中使用 XMLHttpRequest 多數 Web 應用程序都使用請求/響應模型從服務器上獲得完整的 HTML 頁面。常常是點擊一個按鈕&#xff0…

Provisioning Services 7.8 入門系列教程之十一 通過版本控制自動更新虛擬磁盤

續Provisioning Services 7.8 入門系列教程之十 通過類自動更新虛擬磁盤從前兩的兩種更新方式可以看出&#xff0c;它們有一個共同的特點&#xff0c;即需要產生&#xff08;復制&#xff09;完成的虛擬磁盤副本&#xff0c;然后進行相關的升級操作。這兩種方法在實際生產中&am…

OC面試題

什么是KVC和KVO&#xff1f; 答&#xff1a;KVC(Key-Value-Coding)內部的實現&#xff1a;一個對象在調用setValue的時候&#xff0c; &#xff08;1&#xff09;首先根據方法名找到運行方法的時候所需要的環境參數。 &#xff08;2&#xff09;他會從自己isa指針結合環境參數&…

【算法】QuickSort

快速排序&#xff0c;時間復雜度O(N*logN)&#xff0c;要能熟練掌握&#xff01; 以下主要參考http://blog.csdn.net/morewindows/article/details/6684558&#xff0c; 感謝原博主&#xff01; 該方法的基本思想是&#xff1a; 1&#xff0e;先從數列中取出一個數作為基準數。…

串口之GetCommState、SetCommState函數詳解

GetCommState 讀取串口設置(波特率,校驗,停止位,數據位等).函數聲明&#xff1a;BOOL GetCommState(HANDLE hFile,LPDCB lpDCB);GetCommState函數的第一個參數hFile是由CreateFile函數返回指向已打開串行口的句柄。第二個參數指向設備控制塊DCB。如果函數調用成功&#xff0c;則…

登錄失敗時記住訪問的地址

登錄失敗時記住訪問的地址 使用spring MVC 訪問時,在攔截器中記錄訪問的地址: Java代碼 String path request.getRequestURI();//"/demo_channel_terminal/news/list" System.out.println("您無權訪問:" path); //用于登錄成功…