正文

codevs1222信与信封的问题

Achen  Achen  2022-09-20  117

关键词：

二分图匹配。

先匹配一次，一定是完美匹配。然后枚举每条边，去掉它，若是不能完美匹配，这条边就必须。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
typedef long long LL;
const int maxn=100+5;
int cnt,n,a[maxn][maxn],pre[maxn],vis[maxn],x,y;
using namespace std;
int find(int x) {
    for(int i=1;i<=n;i++) 
        if(a[x][i]&&!vis[i]) {
            vis[i]=1;
            if(!pre[i]||find(pre[i])) {
                pre[i]=x;
                return 1;        
            }
        }
    return 0;
}
int main()
{

    scanf("%d",&n);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=1;
    for(;;) {
        scanf("%d%d",&x,&y);
        if(x==0&&y==0) break;
        a[x][y]=0;
    }
    for(int i=1;i<=n;i++) {
        memset(vis,0,sizeof(vis));
        find(i);
    }
    for(int i=1;i<=n;i++) {
        int fl=1;
        for(int j=1;j<=n;j++) if(a[i][j]){
            a[i][j]=0;
            memset(vis,0,sizeof(vis));
            if(pre[j]==i) {
             pre[j]=0;
             if(!find(i)){
             printf("%d %d
",i,j); 
             fl=0; a[i][j]=1; pre[j]=i;
             break;}
             //pre[j]=i;
            }
            a[i][j]=1;
        }
        if(fl) cnt++;
    }
    if(cnt==n) cout<<"none"<<endl;
    return 0;
}

View Code

注意把边去掉后要加回去，pre去掉后若是没匹配上要加回去。

想起了之前轩神出的一道考题。侦探那题，若是删除某点后不能达到限制，则一定有该点。不是正解但是有人卡过了，不知道是数据水还是可以卡过。

codevs1222信与信封的问题

题目描述 DescriptionJohn先生晚上写了n封信，并相应地写了n个信封将信装好，准备寄出。但是，第二天John的儿子Small John将这n封信都拿出了信封。不幸的是，Small John无法将拿出的信正确地装回信封中了。将Small John... 查看详情

codevs1222信与信封的问题

二分图匹配。先匹配一次，一定是完美匹配。然后枚举每条边，去掉它，若是不能完美匹配，这条边就必须。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#include<queue>#include<vect 查看详情

codeves1222

思路：先得到最大匹配，不为n，none，对于每个边,假如不可获缺,那么没有它一定无法完美匹配,对匹配的边依次删除,如果不能完美匹配就输出1#include<bits/stdc++.h>2usingnamespacestd;3constintN=102;45inta[N][N],vis[N];6intc[N],d[N];7intn;8boolFind(... 查看详情

codevs1047邮票面值设计

...石Diamond 题目描述 Description 给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值查看详情

codevs1047邮票面值设计

... 空间限制:128000KB)题目描述 Description 给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1～MAX之间的每一个... 查看详情

算法：字母和信封配对

】算法：字母和信封配对【英文标题】：Algorithm:Lettersandenvelopespairing【发布时间】：2014-01-2212:17:21【问题描述】：免责声明：这不是任何形式的作业，这个问题只是在我浏览所有圣诞贺卡时才想到的问题如下：我们有M个信封和N... 查看详情

两个信封问题

两个信封里面装着x，2x的钱，怎样的策略使获得的收益最优。拿到一个信封，有一次交换的机会：若拿到信封未拆开看，则换与不换收益一样，均为，3x/2元；若拿到信封拆开看，有x元钱，... 查看详情

洛谷p1595信封问题

P1595信封问题题目描述某人写了n封信和n个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。输入输出格式输入格式：一个信封数n输出格式：一个整数，代表有多少种情况。输入输出样例输入样例#1... 查看详情

洛谷——p1595信封问题

P1595信封问题题目描述某人写了n封信和n个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。输入输出格式输入格式：一个信封数n（n<=20）输出格式：一个整数，代表有多少种情况。&n... 查看详情

洛谷p1595信封问题

P1595信封问题最新讨论==题目描述某人写了n封信和n个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。输入输出格式输入格式：一个信封数n 输出格式：一个整数，代表有多少种情... 查看详情

俄罗斯套娃信封问题(代码片段)

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w,h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算最多能有多少个信封能组成... 查看详情

伯努利错装信封问题

题目描述某人写了n封信和n个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。输入输出格式输入格式：一个信封数n（n<=20）输出格式：一个整数，代表有多少种情况。输入输出样例输入... 查看详情

洛谷p1595信封问题

题目描述某人写了n封信和n个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。输入输出格式输入格式：一个信封数n（n<=20）输出格式：一个整数，代表有多少种情况。输入输出... 查看详情

[数学]错排问题

错排问题直接上题解释吧LuoguP1595信封问题题目描述某人写了(n)封信和(n)个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。输入格式一个信封数(n)（(nle20)）输出格式一个整数，代表有多少种情况。... 查看详情

p1595信封问题(代码片段)

WCF 服务客户端：定制的肥皂信封未在线发送

】WCF服务客户端：定制的肥皂信封未在线发送【英文标题】：WCFserviceclient:Customizedsoapenvelopenotbeingsentonthewire【发布时间】：2014-06-0219:30:10【问题描述】：我正在从WCF客户端调用第3方Web服务。问题是该服务需要特定的肥皂信封格... 查看详情

安卓微信与苹果微信的区别？

参考技术A自从接触微信公众号开发以来，就经常会出现一些兼容问题，比如视频再安卓上能播放但是在苹果手机微信上却不可以播放，今天又遇到了视频在手机上不能播放，但是在开发者工具可以播放的问题这引发了我的一个... 查看详情