| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:贴数据了 附代码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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator