程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj 1143: [CTSC2008]祭祀river / 2718: [Violet 4]畢業旅行,bzojctsc2008

bzoj 1143: [CTSC2008]祭祀river / 2718: [Violet 4]畢業旅行,bzojctsc2008

編輯:C++入門知識

bzoj 1143: [CTSC2008]祭祀river / 2718: [Violet 4]畢業旅行,bzojctsc2008


1143: [CTSC2008]祭祀river

Time Limit: 10 Sec  Memory Limit: 162 MB

Description

  在遙遠的東方,有一個神秘的民族,自稱Y族。他們世代居住在水面上,奉龍王為神。每逢重大慶典, Y族都 會在水面上舉辦盛大的祭祀活動。我們可以把Y族居住地水系看成一個由岔口和河道組成的網絡。每條河道連接著 兩個岔口,並且水在河道內按照一個固定的方向流動。顯然,水系中不會有環流(下圖描述一個環流的例子)。

 

  由於人數眾多的原因,Y族的祭祀活動會在多個岔口上同時舉行。出於對龍王的尊重,這些祭祀地點的選擇必 須非常慎重。准確地說,Y族人認為,如果水流可以從一個祭祀點流到另外一個祭祀點,那麼祭祀就會失去它神聖 的意義。族長希望在保持祭祀神聖性的基礎上,選擇盡可能多的祭祀的地點。

Input

  第一行包含兩個用空格隔開的整數N、M,分別表示岔口和河道的數目,岔口從1到N編號。接下來M行,每行包

 

含兩個用空格隔開的整數u、v,描述一條連接岔口u和岔口v的河道,水流方向為自u向v。 N ≤ 100 M ≤ 1 000

Output

  第一行包含一個整數K,表示最多能選取的祭祀點的個數。

Sample Input

4 4
1 2
3 4
3 2
4 2

Sample Output

2

【樣例說明】
在樣例給出的水系中,不存在一種方法能夠選擇三個或者三個以上的祭祀點。包含兩個祭祀點的測試點的方案有兩種:
選擇岔口1與岔口3(如樣例輸出第二行),選擇岔口1與岔口4。
水流可以從任意岔口流至岔口2。如果在岔口2建立祭祀點,那麼任意其他岔口都不能建立祭祀點
但是在最優的一種祭祀點的選取方案中我們可以建立兩個祭祀點,所以岔口2不能建立祭祀點。對於其他岔口
至少存在一個最優方案選擇該岔口為祭祀點,所以輸出為1011。

HINT

先floyd傳遞閉包,再求最小路徑覆蓋

常用定理: 
  最小點覆蓋=最大匹配。 
  最小邊覆蓋=最大獨立集=圖中點的個數-最大匹配。 
  最長反鏈=最小路徑覆蓋=原圖的節點數-新圖最大匹配。

 

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define N 210
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,pp[N],dis[N],u,v,ans,tim;
bool mp[N][N];
bool dfs(int x)
{
    for(int i=1;i<=n;i++) if(mp[x][i])
    {
        if(dis[i]==tim) continue;
        dis[i]=tim;
        if(!pp[i]||dfs(pp[i])){pp[i]=x;return 1;}
    }
    return 0;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        u=read();v=read();
        mp[u][v]=1;
    }
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        mp[i][j]|=mp[i][k]&mp[k][j];
    ans=n;
    for(int i=1;i<=n;i++) tim++,ans-=dfs(i);
    printf("%d\n",ans);
    return 0;
}

 

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