题解 - Vijos

5

妈的50的范围吓的我一愣
。。。。。
好好的O（n）贪心题跑你mmp的网络流。。。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <cstring>
#include <ctime>
#include <vector>
#define inf 1e9
#define ll long long
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Dow(i,j,k) for(int i=k;i>=j;i--)
using namespace std;
int n,k,in[51],out[51],ans=1e9;
char s[51];
int main()
{
    scanf("%d%d",&n,&k);
    For(i,1,n)
    {
        scanf("%s",s+1);
        For(j,1,n)  if(s[j]=='Y') in[i]++,out[j]++;
    }
    For(i,1,n)  ans=min(ans,min(out[i],in[i]));
    printf("%d",min(n,ans+k));
}

1

Sky1231 (sky1231) LV 10 @ 7 年前

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m;
int a[51];
int b[51];
char s[51];

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for (int i=1;i<=n;i++)
        {
            memset(s,0,sizeof(s));
            scanf("%s",s+1);
            for (int j=1;j<=n;j++)
                if (s[j]=='Y')
                    a[i]++,b[j]++;
        }
        int ans=oo_max;
        for (int i=1;i<=n;i++)
            ans=min(ans,min(a[i],b[i]));
        printf("%d\n",min(n,ans+m));
    }
}

sky1231 @ 7 年前

很H2O的题

1

freefood LV 10 @ 11 年前

用一个逗比的方法水过了，拆点，如果男女相互喜欢就原来的点连在一起，如果不喜欢就把两个拆出来的点连在一起，男生连拆出来的点一个容量为k的边，女生拆出来的点连女生原点一个容量为k的边，然后男生连s点一条容量为1，女生连t点一条容量为1，然后跑最大流，如果流量为n就方案数+1，然后再把s连男生的边容量重新改为1，女生连t的边容量重新改为1，重新跑一次。直到流量＜n，这时输出方案数就是答案了&……

测试数据 #0: Accepted, time = 0 ms, mem = 4260 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 4264 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 4260 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 4264 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 4260 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 4260 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 4264 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 4260 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 4256 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 4264 KiB, score = 10
Accepted, time = 30 ms, mem = 4264 KiB, score = 100

0

Antinomy LV 8 @ 8 年前

测试数据 #0: Accepted, time = 0 ms, mem = 1552 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 1552 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1556 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1556 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1564 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1696 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1700 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1832 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1832 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 1832 KiB, score = 10
Accepted, time = 30 ms, mem = 1832 KiB, score = 100
代码

三次TLE到处找地方优化。。然后发现是数组开小了。。可开小了居然不是RE而是TLE这是什么情况。。。
感谢dalao们给的思路，网络流的话建模方法在下面的注释里。。
还有很长的路啊。。

#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<sstream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<math.h>
#include<map>
#include<cctype>
#include<queue>
#include<functional>
#include<set>
#define Mem(a,b) memset((a),(b),sizeof((a)))
#define Sy system("pause")
const int maxn = 1000;
const int INF = 0x3f3f3f;
using namespace std;


struct Dinic{
    struct Edge {
        int from, to, cap, flow;
        Edge(int a, int b, int c, int d) :from(a), to(b), cap(c), flow(d) {}
        Edge(){}
        friend bool operator < (const Edge& a, const Edge& b) {
            return a.from < b.from || (a.from == b.from && a.to < b.to);
        }
    };

    int n, m, s, t;
    vector<Edge> edges;//边数两倍
    vector<int> G[maxn];
    bool vis[maxn]; // BFS使用
    int d[maxn];
    int cur[maxn];

    void init(int n){
         this->n = n;
         for (int i = 0; i < n; i += 1) G[i].clear();
        edges.clear();
     }

    void AddEdge(int from, int to, int cap){
        edges.push_back(Edge(from, to, cap, 0));
        edges.push_back(Edge(to, from, 0, 0));
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }

    bool BFS(){  //构建层次网络，如果构建的时候汇点没有访问过证明已经不在网络中
        Mem(vis, 0);
        queue<int> Q;
        Q.push(s);
        vis[s] = 1;
        d[s] = 0;
        while (!Q.empty()){
            int x = Q.front(); Q.pop();
            for (int i = 0; i<G[x].size(); i += 1){
                Edge & e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow){
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;//层次
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x, int a){
        if (x == t || a == 0) return a;//如果已经到汇点或者增量是0，没必要继续因为已经找到了最大流
        int flow = 0, f;
        for (int & i = cur[x]; i<G[x].size(); i += 1){
            Edge& e = edges[G[x][i]];
            //如果e.to是x的儿子结点并且其增量大于0
            if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0){
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (!a) break;
            }
        }
        return flow;
    }

    int MaxFlow(int s, int t){
        this->s = s; this->t = t;
        int flow = 0;
        while (BFS()){
            Mem(cur, 0);
            flow += DFS(s, INF);
        }
        return flow;
    }
};

/* 

一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。
有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。

第一行包含两个整数n和k。以下n行每行包含n个字符，其中第i行第j个字符为'Y'当且仅当男孩i和女孩j相互喜欢。

n<=50，k<=30；
*/


char Like[maxn][maxn];
int main(){
    int n, k;
    scanf("%d %d", &n, &k);
//  memset(Like, 0, sizeof(Like));

    int S = 0, T = 4 * n + 1;
    for (int i = 1; i <= n; i += 1){
        scanf("%s", &Like[i]);
    }
    /*

    S -(a)-> Mx   Fy -(a)-> T
    Mx -(k)- My    Fx -(k)-> Fy
    如果相互喜欢，Mx -(1)-> Fy
    否则    My -(1)-> Fx
    二分枚举a

    S: 0 Mx:[1,n] My:[n+1,2n]  Fx:[2n+1,3n]  Fy:[3n+1,4n] T:4n+1
    */
    int ans;
    int l = 0, r = 50;
    Dinic D;
    while (l <= r){
        D.init(4 * n + 2);
        int mid = (l + r) >> 1;
        for (int i = 1; i <= n; i += 1){
            D.AddEdge(S, i, mid); // S - Mx
            D.AddEdge(i + 3 * n, T, mid);// Fy - T
            D.AddEdge(i, i + n, k);// Mx - My
            D.AddEdge(i + 2 * n, i + 3 * n, k);// Fx - Fy
            for (int j = 1; j <= n; j += 1){
                if (Like[i][j - 1] == 'Y') D.AddEdge(i, j + 3 * n, 1); //Mx - Fy
                else D.AddEdge(i + n, j + 2 * n, 1);  //My - Fx
            }
        }
        int tmp = D.MaxFlow(S, T);
        if (tmp >= n*mid) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    printf("%d\n", ans);
    //Sy;
    return 0;
}

0

JSZX11556 LV 9 @ 9 年前

http://www.cnblogs.com/JSZX11556/p/4631531.html 网络流

0

nzhtl1477 LV 10 @ 9 年前

P1521跳舞Accepted
记录信息
评测状态 Accepted
题目 P1521 跳舞
递交时间 2016-01-08 21:22:38
代码语言 C++
评测机 ShadowShore
消耗时间 30 ms
消耗内存 12352 KiB
评测时间 2016-01-08 21:22:40
评测结果
编译成功

foo.cpp: In function 'bool bfs()':
foo.cpp:44:58: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( register int i = 0 ; i < linker[ now ].size() ; i++ )
^
foo.cpp: In function 'int dinic(int, int)':
foo.cpp:54:63: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( register int i = cur[ now ] ; i < linker[ now ].size() ; i++ )
^
foo.cpp: In function 'bool check(int)':
foo.cpp:77:46: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
while( bfs() ) while( temp = dinic( s , inf ) ) ans += temp;
^
测试数据 #0: Accepted, time = 0 ms, mem = 12304 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 12304 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 12312 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 12312 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 12308 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 12336 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 12328 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 12352 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 12352 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 12336 KiB, score = 10
Accepted, time = 30 ms, mem = 12352 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
#include <string.h>
#define s 0
#define t 208
#define inf 1000000000

using namespace std;

struct edge
{
int x , y , cap;
edge() {}
edge( int x , int y , int z ) : x( x ) , y( y ) , cap( z ) {}
}e[1000000];

int n , k , pos , x , y , z;
vector < int > linker[200 + 10];
int ans , l , r , mid;
int dist[200 + 10] , cur[200 + 10];
char sd[50 + 2];

inline void addedge( int x , int y , int z )
{
linker[ x ].push_back( pos );
e[ pos++ ] = edge( x , y , z );
linker[ y ].push_back( pos );
e[ pos++ ] = edge( y , x , 0 );
}

inline bool bfs()
{
queue < int > q;
q.push( s );
memset( dist , -1 , sizeof( dist ) );
memset( cur , 0 , sizeof( cur ) );
int now;
dist[s] = 0;
while( !q.empty() )
{
now = q.front() , q.pop();
for( register int i = 0 ; i < linker[ now ].size() ; i++ )
if( dist[ e[ linker[ now ][i] ].y ] == -1 && e[ linker[ now ][i] ].cap ) q.push( e[ linker[ now ][i] ].y ) , dist[ e[ linker[ now ][i] ].y ] = dist[ now ] + 1;
}
return dist[ t ] > 0;
}

inline int dinic( int now , int low )
{
if( now == t || !low ) return low;
int temp;
for( register int i = cur[ now ] ; i < linker[ now ].size() ; i++ )
{
cur [ now ] = i;
if( dist[ e[ linker[ now ][i] ].y ] == dist[ now ] + 1 && e[ linker[ now ][i] ].cap && ( temp = dinic( e[ linker[ now ][i] ].y , min( low , e[ linker[ now ][i] ].cap ) ) ) )
{
e[ linker[ now ][i] ].cap -= temp;
e[ linker[ now ][i] ^ 1 ].cap += temp;
return temp;
}
}
return 0;
}

inline bool check( int x )
{
int now = 0;
for( register int i = 1 ; i <= n << 1 ; i++ )
e[ now ].cap = x , e[ now ^ 1 ].cap = 0 , now += 2;
for( register int i = 1 ; i <= n << 1 ; i++ )
e[ now ].cap = k , e[ now ^ 1 ].cap = 0 , now += 2;
for( register int i = now ; i < pos ; i += 2 )
e[i].cap = 1 , e[i ^ 1].cap = 0;
int ans = 0 , temp;
while( bfs() ) while( temp = dinic( s , inf ) ) ans += temp;
return ans >= x * n;
}

int main()
{
scanf( "%d %d", &n , &k );
for( register int i = 1 ; i <= n ; i++ ) addedge( s , i , 0 );
for( register int i = 1 ; i <= n ; i++ ) addedge( n + i , t , 0 );
for( register int i = 1 ; i <= n ; i++ ) addedge( i , i + 105 , k );
for( register int i = 1 ; i <= n ; i++ ) addedge( i + n + 105 , i + n , k );
for( register int i = 1 ; i <= n ; i++ )
{
scanf( "%s", sd );
for( register int j = 1 ; j <= n ; j++ )
if( sd[j - 1] == 'Y' ) addedge( i , j + n , 1 );
else addedge( i + 105 , j + n + 105 , 1 );
}
l = 0 , r = 50 + 2;
while( l <= r )
{
mid = ( l + r ) >> 1;
if( check( mid ) ) ans = mid , l = mid + 1;
else r = mid - 1;
}
cout << ans << endl;
return 0;
}

0

绿色的云 LV 10 @ 11 年前

这道题有两种解法，一种贪心，一种网络流。貌似如果改成单向就要网络流。。
编译成功

foo.cpp: In function 'int main()':
foo.cpp:20:22: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[51]' [-Wformat]
测试数据 #0: Accepted, time = 0 ms, mem = 432 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 436 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 444 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 436 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 432 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 440 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 440 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 440 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 440 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 440 KiB, score = 10
Accepted, time = 0 ms, mem = 444 KiB, score = 100
贪心很短。。。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>

using namespace std;

#define MAXN 51

int girl[MAXN],boy[MAXN];
int n,k;
char c[MAXN];
int ans=0x7fffffff;

int main(){
memset(girl,0,sizeof(girl));
memset(boy,0,sizeof(boy));
scanf("%d%d",&n,&k);
for (int i=0;i++<n;){
scanf("%s",&c);
for (int j=0;j<n;j++){
if (c[j]=='Y'){
boy[i]++;
girl[j+1]++;
}
}
}
for (int i=0;i++<n;){
ans=min(ans,girl[i]);
ans=min(ans,boy[i]);
}
ans+=k;
ans=min(ans,n);
printf("%d\n",ans);
return 0;
}

0

我是姜逸伦大神 LV 8 @ 14 年前

这种水题我都不想说了

0

我是天才他哥 LV 10 @ 14 年前

SAP缓缓慢慢的水过了

0

尖端才子 LV 10 @ 15 年前

水题……枚举答案……然后SAP即可……

数据竟然如此之弱……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

0

xiaoX LV 10 @ 15 年前

枚举答案时只要在之前的残量网络上修改一些边的容量即可，应该比每次都重新建图要快的多吧

我这样做用邻接矩阵dinic秒杀

0

陈亮宇 LV 10 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

拆了点。。竟然 maxn 还是赋值成 50 。。。晕。

0

zhh1993 LV 10 @ 15 年前

郁闷数组赋值这步啊啊,太慢了……

于是乎……

朴素网络流=超时,加N次小优化=

Accepted 有效得分：100 有效耗时：741ms

不服气，就写个Dicinic试试,虽然数组赋值频率好像更高...

可是结果是 Accepted 有效得分：100 有效耗时：0ms

看来还是不能怕麻烦……Dicnic万岁~~

0

zhanghanyuan LV 10 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

数据好弱啊，没限制K还能过9个。。。

0

violethill LV 10 @ 15 年前

一条件露了弄了我一晚上

没看到女孩也最多愿意和不喜欢的男孩跳k次，以为只有男孩最多愿意和女孩跳k次

我说怎么都拆4个点

害我拆3个点的弄了一晚上还在80

0

panzer_wy LV 10 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 805ms

├ 测试数据 09：答案正确... 165ms

├ 测试数据 10：答案正确... 40ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1010ms

这种题目用了这么长时间，无语中………………

枚举答案真的那么慢吗 ⊙﹏⊙b

可能是因为偷懒用邻接矩阵的关系…………

补充：方法：最大流+枚举答案限流

0

OIWinner LV 10 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

直接模拟都0ms秒杀，可见数据之弱。

0

song19931218 LV 9 @ 15 年前

我快要崩溃了，调了N久

终于调出来了

采用了DD牛的多叉增广。。。

不过由于是用邻接矩阵写的，所以效率不是很高

一开始想用指针写，可是由于这一道题目需要多次调用原来的流网络，所以放弃了，不知各位大牛有没有办法，Orz OrzOrzOrzOrzOrzOrzOrzOrz

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

0

wll969 LV 8 @ 15 年前

我算长见识了，原来过8个点的程序也可能是完全错的

0

icedotwqw LV 3 @ 15 年前

program li;

var n,min,k,i,j:longint;

　　s:array[0..1500] of string;

　　boy,gril:array[0..1500] of longint;

begin

readln(n,k);

for i:= 1 to n do readln(s[i]);

for i:= 1 to n do begin boy[i]:=0; gril[i]:=0; end;

for i:= 1 to n do

for j:= 1 to n do

　　if s[i][j]='Y' then

　　 begin inc(boy[i]); inc(gril[j]); end;

min:=maxlongint;

for i:= 1 to n do

if min>boy[i] then min:=boy[i];

for i:= 1 to n do

if min>gril[i] then min:=gril[i];

if min+k>n then writeln(n)

else writeln(min+k);

end.

题解

37 条题解

跳舞

信息

状态

开发

支持

题解

37 条题解

跳舞

信息

状态

开发

支持

还没有账户？

登录