poj1325

给出一系列任务，每个任务可以在机器A的某个模式，或者在机器B的某个模式下完成。机器A和B每切换一次模式需要重启一次。问完成这些任务，最少需要重启机器多少次？

把任务看作边 “重启”操作看作点

这道题就是一个裸的二分图最小点覆盖

然后呢最小点覆盖 NP完全问题

艹

然后呢二分图中最小点覆盖等于最大匹配

我真是做TMD无敌棒槌终极骚猪喷香油水水之终极猪皮皮之麻辣臭皮小骚猪

好的好的随便写个匈牙利10分钟AC

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#include<cstring>

using namespace std;

const int Max=;

int n,m,yM[Max];

bool vis[Max],map[Max][Max];

bool SearchPath(int u)

{

 for(int v=;v<m;v++)

  if(!vis[v] && map[u][v])

  {

   vis[v]=true;

   if(yM[v]==- || SearchPath(yM[v]))

   {

    yM[v]=u;

    return true;

   }

  }

 return false;

}

int MaxMatch()

{

 int u,ret=;

 memset(yM,-,sizeof(yM));

 for(u=;u<n;u++)

 {

  memset(vis,false,sizeof(vis));

  if(SearchPath(u))

   ret++;

 }

    return ret;

}

int main()

{

 int i,k,u,v;

 while(scanf("%d",&n),n)

 {

  scanf("%d%d",&m,&k);

  memset(map,,sizeof(map));

  while(k--)

  {

   scanf("%d%d%d",&i,&u,&v);

   if(u!=&&v!=) //如果有一个有0，则这个工作不用重启时间

    map[u][v]=;

  }

        cout<<MaxMatch()<<endl;

 }

 return ;

}

巴特西

poj1325

最新文章

热门文章