BZOJ 1191: [HNOI2006]超级英雄Hero

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
题解

Description

现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”，比如求助现场观众，或者去掉若干个错误答案（选择题）等等。这里，我们把规则稍微改变一下。假设主持人总共有m道题，选手有n种不同的“锦囊妙计”。主持人规定，每道题都可以从两种“锦囊妙计”中选择一种，而每种“锦囊妙计”只能用一次。我们又假设一道题使用了它允许的锦囊妙计后，就一定能正确回答，顺利进入下一题。现在我来到了节目现场，可是我实在是太笨了，以至于一道题也不会做，每道题只好借助使用“锦囊妙计”来通过。如果我事先就知道了每道题能够使用哪两种“锦囊妙计”，那么你能告诉我怎样选择才能通过最多的题数吗？

Input

输入文件的一行是两个正整数n和m(0 < n <1001,0 < m < 1001)表示总共有n中“锦囊妙计”，编号为0~n-1，总共有m个问题。
以下的m行，每行两个数，分别表示第m个问题可以使用的“锦囊妙计”的编号。
注意，每种编号的“锦囊妙计”只能使用一次，同一个问题的两个“锦囊妙计”可能一样。

Output

第一行为最多能通过的题数p

Sample Input

5 6
3 2
2 0
0 3
0 4
3 2
3 2

Sample Output

题解

这道题目一言就想到了二分+最大流验证的方法！QuQ可是TLE了。

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int Maxm=1010;
const int Maxn=1010;
const int Inf=2147483647;
struct Edge{
    int v,nxt,f;
    Edge(){}
    Edge(int a,int b,int c){
        v=a;f=b;nxt=c;
    }
};
Edge e[Maxn*Maxn*2+4*Maxn+10];
int nume;
int head[Maxn];
inline void addEdge(int u,int v,int f){
    e[++nume]=Edge(v,f,head[u]);
    head[u]=nume;
    e[++nume]=Edge(u,0,head[v]);
    head[v]=nume;
}
queue<int> que;
int dist[Maxn];
int src,sink;
inline bool spfa(){
    while(!que.empty()) que.pop();
    memset(dist,-1,sizeof(dist));
    dist[src]=0;
    que.push(src);
    while(!que.empty()){
        int now=que.front();
        que.pop();
        for (int i=head[now];i;i=e[i].nxt){
            int v=e[i].v;
            if (e[i].f>0 && dist[v]==-1){
                dist[v]=dist[now]+1;
                que.push(v);
            }
        }
    }
    return dist[sink]!=-1;
}
inline int remin(int a,int b){return (a<b?a:b);}
int dfs(int x,int delta){
    if (x==sink) return delta;
    int ret=0;
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v;
        if (e[i].f>0 && dist[v]==dist[x]+1){
            int ddelta=dfs(v,remin(e[i].f,delta));
            delta-=ddelta;
            e[i].f-=ddelta;
            e[i^1].f+=ddelta;
            ret+=ddelta;
        }
    }
    return ret;
}
inline int dinic(){
    int ret=0;
    while(spfa()) ret+=dfs(src,Inf);
    return ret;
}
int n,m;
struct Query{
    int x,y;
};
Query qey[Maxn];
inline void init(){
    nume=1;
    memset(head,0,sizeof(head));
}
inline void rebuild(int mid){
    src=n+m+1;
    sink=n+m+2;
    for (int i=1;i<=n;i++) addEdge(src,i,1);
    for (int i=1;i<=mid;i++) addEdge(n+i,sink,1);
    for (int i=1;i<=mid;i++){
        addEdge(qey[i].x,n+i,1);
        addEdge(qey[i].y,n+i,1);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) scanf("%d%d",&qey[i].x,&qey[i].y);
    for (int i=1;i<=m;i++) {qey[i].x++;qey[i].y++;}
    int left=1,right=m;
    int Ans=0;
    while(left<=right){
        int mid=(left+right)/2;
        init();
        rebuild(mid);
        if (dinic()==mid){
            left=mid+1;
            Ans=mid;
        }else{
            right=mid-1;
        }
    }
    printf("%d\n",Ans);
    return 0;
}

100

101

102

103

104

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int Maxm=1010;

const int Maxn=1010;

const int Inf=2147483647;

struct Edge{

int v,nxt,f;

Edge(){}

Edge(int a,int b,int c){

v=a;f=b;nxt=c;

}

};

Edge e[Maxn*Maxn*2+4*Maxn+10];

int nume;

int head[Maxn];

inline void addEdge(int u,int v,int f){

e[++nume]=Edge(v,f,head[u]);

head[u]=nume;

e[++nume]=Edge(u,0,head[v]);

head[v]=nume;

}

queue<int> que;

int dist[Maxn];

int src,sink;

inline bool spfa(){

while(!que.empty()) que.pop();

memset(dist,-1,sizeof(dist));

dist[src]=0;

que.push(src);

while(!que.empty()){

int now=que.front();

que.pop();

for (int i=head[now];i;i=e[i].nxt){

int v=e[i].v;

if (e[i].f>0 && dist[v]==-1){

dist[v]=dist[now]+1;

que.push(v);

}

return dist[sink]!=-1;

}

inline int remin(int a,int b){return (a<b?a:b);}

int dfs(int x,int delta){

if (x==sink) return delta;

int ret=0;

for (int i=head[x];i;i=e[i].nxt){

int v=e[i].v;

if (e[i].f>0 && dist[v]==dist[x]+1){

int ddelta=dfs(v,remin(e[i].f,delta));

delta-=ddelta;

e[i].f-=ddelta;

e[i^1].f+=ddelta;

ret+=ddelta;

}

return ret;

}

inline int dinic(){

int ret=0;

while(spfa()) ret+=dfs(src,Inf);

return ret;

}

int n,m;

struct Query{

int x,y;

};

Query qey[Maxn];

inline void init(){

nume=1;

memset(head,0,sizeof(head));

}

inline void rebuild(int mid){

src=n+m+1;

sink=n+m+2;

for (int i=1;i<=n;i++) addEdge(src,i,1);

for (int i=1;i<=mid;i++) addEdge(n+i,sink,1);

for (int i=1;i<=mid;i++){

addEdge(qey[i].x,n+i,1);

addEdge(qey[i].y,n+i,1);

}

int main(){

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

for (int i=1;i<=m;i++) scanf("%d%d",&qey[i].x,&qey[i].y);

for (int i=1;i<=m;i++) {qey[i].x++;qey[i].y++;}

int left=1,right=m;

int Ans=0;

while(left<=right){

int mid=(left+right)/2;

init();

rebuild(mid);

if (dinic()==mid){

left=mid+1;

Ans=mid;

}else{

right=mid-1;

}

printf("%d\n",Ans);

return 0;

}

人生还能在艰难一点点嘛？于是我在网上找到了这个并查集的做法！【其实是因为我不会匈牙利

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 10000
int ptr[MAXN][2];
int near[MAXN];
bool vis[MAXN];
bool find(int now)
{
  int i;
  if (vis[now])return false;
  vis[now]=true;
  for (i=0;i<2;i++)
  {
    if (near[ptr[now][i]]==-1 || find(near[ptr[now][i]]))
    {
      near[ptr[now][i]]=now;
      return true;
    }
  }
  return false;
}
int main()
{
  int n,m;
  scanf("%d%d",&n,&m);
  int i;
  int x,y;
  memset(near,-1,sizeof(near));
  for (i=0;i<m;i++)
  {
    scanf("%d%d",&x,&y);
    ptr[i][0]=x;
    ptr[i][1]=y;
  }
  for (i=0;i<m;i++)
  {
    memset(vis,0,sizeof(vis));
    if (!find(i))break;
  }
  printf("%d\n",i);
  return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define MAXN 10000

int ptr[MAXN][2];

int near[MAXN];

bool vis[MAXN];

bool find(int now)

{

int i;

if (vis[now])return false;

vis[now]=true;

for (i=0;i<2;i++)

{

if (near[ptr[now][i]]==-1 || find(near[ptr[now][i]]))

{

near[ptr[now][i]]=now;

return true;

}

return false;

}

int main()

{

int n,m;

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

int i;

int x,y;

memset(near,-1,sizeof(near));

for (i=0;i<m;i++)

{

scanf("%d%d",&x,&y);

ptr[i][0]=x;

ptr[i][1]=y;

}

for (i=0;i<m;i++)

{

memset(vis,0,sizeof(vis));

if (!find(i))break;

}

printf("%d\n",i);

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑