Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:贴数据了 附代码

Posted by dsfhlha at 2013-12-01 13:40:29 on Problem 1087
In Reply To:Re:贴数据了 附代码 Posted by:dsfhlha at 2013-12-01 13:26:42
确定是费用流模板错了,是不是模板要改些什么数据?还是 重边问题?

> 其他数据都对,就这组算出来是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;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator