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