hdu-2444-二分圖判定+最大分配

来源:http://www.cnblogs.com/llsq/archive/2016/09/25/5906169.html
-Advertisement-
Play Games

The Accomodation of Students Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5451 Accepted Submis ...


The Accomodation of Students

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5451    Accepted Submission(s): 2491


Problem Description There are a group of students. Some of them may know each other, while others don't. For example, A and B know each other, B and C know each other. But this may not imply that A and C know each other.

Now you are given all pairs of students who know each other. Your task is to divide the students into two groups so that any two students in the same group don't know each other.If this goal can be achieved, then arrange them into double rooms. Remember, only paris appearing in the previous given set can live in the same room, which means only known students can live in the same room.

Calculate the maximum number of pairs that can be arranged into these double rooms.  

 

Input For each data set:
The first line gives two integers, n and m(1<n<=200), indicating there are n students and m pairs of students who know each other. The next m lines give such pairs.

Proceed to the end of file.

 

 

Output If these students cannot be divided into two groups, print "No". Otherwise, print the maximum number of pairs that can be arranged in those rooms.  

 

Sample Input  4  4 1 2 1 3 1 4 2 3  6  5 1 2 1 3 1 4 2 5 3 6  

 

Sample Output No 3

 題目大意:有n個學生,有m對人是認識的,每一對認識的人能分到一間房,問能否把n個學生分成兩部分,每部分內的學生互不認識,而兩部分之間的學生認識。如果可以分成兩部分,就算出房間最多需要多少間,否則就輸出No。

思路:二分判定用染色法,找最大匹配數用匈牙利演算法

代碼:

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
const int MAX=1e5+5;
using namespace std;
vector<int>mp[MAX];
int d[MAX],n,m,vis[MAX],link[MAX];
int dfs(int x,int f)            //染色法
{
    d[x]=f;
    for(int i=0; i<mp[x].size(); i++)
    {
        if(d[x]==d[mp[x][i]])
            return 0;
        int u=mp[x][i];
        if(d[u]==0)
            if(!dfs(u,-f))
                return 0;
    }
    return 1;
}
int dfs2(int x)             //找最大匹配
{
    for(int i=0; i<mp[x].size(); i++)
    {
        int v=mp[x][i];
        if(!vis[v])
        {
            vis[v]=1;
            if(link[v]==-1||dfs2(link[v]))
            {
                link[v]=x;
                return 1;
            }
        }
    }
    return 0;

}
int find()               //找最大匹配
{ 
    int res=0;
    memset(link,-1,sizeof(link));
    for(int i=1; i<=n; i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs2(i))
            res++;
    }
    return res;
}
int main()
{
    int a,b;
    while(cin>>n>>m)
    {
        for(int i=1; i<=n; i++)
            if(mp[i].size())
                mp[i].clear();
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&a,&b);
            mp[a].push_back(b);
            mp[b].push_back(a);
        }
        int flag=1;
        memset(d,0,sizeof(d));
        for(int i=1; i<=n; i++)          //染色
        {
            if(mp[i].size())
                if(!d[i])
                    if(!dfs(i,1))
                    {
                        flag=0;
                        break;
                    }
        }
        if(!flag)
            cout<<"No"<<endl;
        else
        {
            cout<<find()/2<<endl;
        }

    }
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 分別使用序數和enummap的結果: 序數: test1() 使用enummap,tes1t ...
  • 1. Python 文件I/O 本章只講述所有基本的的I/O函數,更多函數請參考Python標準文檔。 2.列印到屏幕 最簡單的輸出方法是用print語句,你可以給它傳遞零個或多個用逗號隔開的表達式。此函數把你傳遞的表達式轉換成一個字元串表達式,並將結果寫到標準輸出如下: 示例1: 運行示例1結果如 ...
  • 【應用場景】:熱門標簽、推薦 【特點】: 在佈局內,隨意擺放任意個view,每行所擺放的view個數,根據實施計算出來的寬度,一旦當前要擺放的view寬度和之前擺放的所有view寬度加在一起,超過了佈局的寬度,那麼就把該view換行擺放。 【佈局】: <LinearLayout xmlns:andr ...
  • maven作為一個項目構建工具,在開發的過程中很受歡迎,可以幫助管理項目中的bao依賴問題,另外它的很多功能都極大的減少了開發的難度,下麵來介紹maven的安裝及與eclipse的集成。 maven的官網地址為:http://maven.apache.org/,打開網頁之後,看到最新的版本是3.3. ...
  • chunkupload簡介 chunkupload是一款基於java語言的斷點續傳組件,針對文件上傳,非文件下載,集成方便,使用簡單。 從整體上講,chunkupload會對文件進行切片處理,每個切片4M大小,預設情況下,chunkupload不會對切片進行合併,筆者也不建議在上傳文件時對切片進行合 ...
  • 時間複雜度O(n)當n比較大時歐拉篩法所用的時間比O(nloglogn)的演算法的時間少的會越來越明顯 為什麼呢? 因為在歐拉篩法中,每一個合數只被訪問並將其所對的f[]的值修改了一次。 ...
  • #include <stdio.h>main(){ int x; printf("請輸入要排序數字個數:"); scanf("%d",&x); int i,j,k,a,b,num[x]; printf("輸入數據:"); for(i=0;i<x;i++) scanf("%d",&num[i]); f ...
  • 1.Quartz 是用來完成任務調度的。 2.Quartz 的三個核心概念:調度器、任務、觸發器。 (1)Job:通過實現該介面來定義需要執行的任務。 (2)JobDetail:Quartz 在每次執行 Job 時,都重新創建一個 Job 實例,所以它不是直接接受一個 Job 的實例,而是接受 Jo ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...