其他数据都对，就这组算出来是3是怎么回事啊？
30
r0
r1
r2
r3
r4
r5
r6
r7
r8
r9
r10
r11
r12
r13
r14
r15
r16
r17
r18
r19
r20
r21
r22
r23
r24
r25
r26
r27
r28
r29
30
d0 p0
d1 p1
d2 p2
d3 p3
d4 p4
d5 p5
d6 p6
d7 p7
d8 p8
d9 p9
d10 p10
d11 p11
d12 p12
d13 p13
d14 p14
d15 p15
d16 p16
d17 p17
d18 p18
d19 p19
d20 p20
d21 p21
d22 p22
d23 p23
d24 p24
d25 p25
d26 p26
d27 p27
d28 p28
d29 p29
100
p15 r19
p12 r21
p12 r11
p7 r2
p10 r16
p29 r4
p3 r17
p23 r28
p27 r1
p18 r2
p3 r29
p5 r8
p14 r9
p23 r0
p29 r0
p18 r14
p19 r22
p27 r24
p3 r5
p18 r5
p21 r10
p10 r17
p27 r25
p15 r16
p27 r4
p18 r22
p25 r15
p0 r9
p25 r23
p1 r16
p16 r11
p0 r27
p3 r19
p13 r29
p24 r2
p4 r8
p4 r6
p2 r2
p9 r21
p28 r19
p13 r24
p4 r14
p3 r21
p29 r27
p7 r15
p8 r29
p13 r12
p19 r18
p20 r7
p5 r16
p6 r22
p9 r8
p25 r18
p29 r15
p9 r4
p18 r13
p2 r25
p25 r10
p24 r0
p14 r5
p19 r17
p3 r1
p17 r8
p18 r15
p23 r27
p23 r10
p8 r14
p25 r7
p10 r21
p17 r12
p16 r4
p14 r10
p5 r21
p8 r24
p0 r11
p17 r17
p11 r5
p2 r26
p25 r17
p6 r25
p23 r24
p24 r12
p29 r28
p11 r1
p19 r20
p5 r5
p24 r19
p7 r21
p10 r7
p7 r11
p10 r25
p20 r22
p22 r15
p18 r17
p24 r17
p4 r18
p11 r29
p22 r2
p3 r8
p15 r0
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

struct Edge
{
    int v, f, nxt;

};
int sr, ed;
const int maxn =200, maxm=200;
const int inf=10000000;
int g[maxn +10];
int nume;
int n,nn, m, k;
Edge e[maxn *2 +10];
void addage(int u, int v, int c)
{
    e[++nume].v =v;
    e[nume].f =c;
    e[nume].nxt =g[u];
    g[u]=nume;             //     g[u]每个顶点发射出去的顶边！！
    e[++nume].v=u;
    e[nume].f=0;
    e[nume].nxt =g[v];
    g[v]=nume;
}

void init()
{
    memset(g, 0, sizeof(g));
    nume =1;

}
queue<int> que;
bool vis[maxn+10];
int dist[maxn+10];
void bfs()
{
    memset (dist, 0, sizeof(dist));
    while(!que.empty()) que.pop();
    vis[sr]=true;
    que.push(sr);
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        for(int i=g[u]; i; i=e[i].nxt)
        {
            if(!vis[e[i].v] && e[i].f)
            {
                que.push(e[i].v);
                dist[e[i].v]=dist[u]+1;
                vis[e[i].v]=true;
            }
        }
    }
}
int dfs(int u, int delta)
{

    if(u==ed)
        return delta;
    else
    {
        int ret=0;
        for(int i=g[u]; i && delta; i=e[i].nxt)
        {
            if(e[i].f && dist[e[i].v] == dist[u] +1)
            {
                int dd =dfs(e[i].v, min(e[i].f, delta));
                e[i].f -= dd;
                e[i ^1].f+=dd;
                delta-=dd;
                ret+=dd;
            }
        }
        return ret;
    }
}
int maxflow()
{

    int ret =0;
    while (true)
    {
        memset(vis, 0, sizeof(vis));
        bfs();
        if(!vis[ed]) return ret;
        ret +=dfs(sr, inf);
    }

}
char c[500][30];
char c1[30], c2[30];
int getnum(char ch[])
{
    for(int i=2; i<=nn+1; i++)
        if(strcmp(c[i], ch)==0)
            return i;
    return -1;
}



int main()
{

    cin >> n;
    nn=n+1;
    sr=0;
    ed=1;
    for(int i=2; i<=n+1; i++)
    {

        cin >> c[i];
        addage(i, 1, 1);
    }
    cin >> m;
    for(int i=1; i<=m; i++)
    {
        cin >> c1 >> c2;
        int num = getnum(c2);
        if(num==-1)
        {
            nn++;
            strcpy(c[nn], c2);
            addage(0, nn, 1);
        }
        else
        {
            addage(0, num, 1);
        }
    }
    cin >> k;
    for(int i=1; i<=k; i++)
    {
        cin >> c1 >> c2;
        int x, y;
        x=getnum(c1);
        y=getnum(c2);
        if(x==-1)
        {
            ++nn;
            strcpy(c[nn], c1);
            x=nn;
        }
        if(y==-1)
        {
            ++nn;
            strcpy(c[nn], c2);
            y=nn;
        }
        addage(x, y, inf);
       // cout << endl << x << " " << y << endl;


    }
    cout << m - maxflow() << endl;
    return 0;
}

• Re:贴数据了 附代码 (4894) dsfhlha 2013-12-01 13:40:29