syhd142  
日历
<2024年10月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789
统计
  • 随笔 - 23
  • 文章 - 122
  • 评论 - 31
  • 引用 - 0

导航

常用链接

留言簿(2)

随笔档案(23)

文章分类(270)

文章档案(122)

我的豆瓣

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 
解法:最大权闭合图,网络流解,也比较裸。
#include <stdio.h>
#include 
<stdlib.h>
#include 
<string.h>

#define N 205
#define INF 1 << 29

bool mark[N];
int g[N][N];

int ISAP(int src, int sink, int n)
{
    
int maxflow = 0, flow, u = src, v, d;
    
int cnt[N], dis[N], pre[N];
    memset(cnt, 
0sizeof(cnt));
    memset(dis, 
0sizeof(dis));
    cnt[
0= n;
    pre[src] 
= src;
    
while(dis[src] < n)
    {
        
if(u == sink)
        {
            flow 
= INF;
            
for(int i = sink; i != src; i = pre[i])
            {
                
if(g[pre[i]][i] < flow)
                    flow 
= g[pre[i]][i];
            }
            maxflow 
+= flow;
            u 
= src;
            
for(int i = sink; i != src; i = pre[i])
            {
                g[pre[i]][i] 
-= flow;
                g[i][pre[i]] 
+= flow;
            }
        }
        
for(d = n, v = 0; v < n; v++)
        {
            
if(!g[u][v]) continue;
            d 
= d < dis[v] ? d : dis[v];
            
if(dis[v] + 1 == dis[u]) break;
        }
        
if(v < n) pre[v] = u, u = v;
        
else
        {
            
if(!(--cnt[dis[u]])) break;
            
++cnt[dis[u] = d + 1];
            
if(u != src) u = pre[u];
        }
    }
    
return maxflow;
}

void dfs(int u, int n)
{
    mark[u] 
= 1;
    
for(int i = 0; i < n; i++)
        
if(!mark[i] && g[i][u])
            dfs(i, n);
}

int main()
{
    
int t, n, m, src, sink, ans1, ans2[N], top;
    
int key, treasure;
    scanf(
"%d"&t);
    
while(t--)
    {
        memset(g, 
0sizeof(g));
        memset(ans2, 
0sizeof(ans2));
        memset(mark, 
0sizeof(mark));
        scanf(
"%d %d"&n, &m);
        src 
= ans1 = top = 0, sink = n + m + 1;
        
for(int i = 1; i <= n; i++)
        {
            scanf(
"%d"&key);
            g[i 
+ m][sink] = key;
        }
        
for(int i = 1; i <= m; i++)
        {
            scanf(
"%d"&treasure);
            g[src][i] 
= treasure;
            ans1 
+= treasure;
        }
        
for(int i = 1; i <= m; i++)
        {
            
int num, id;
            scanf(
"%d"&num);
            
for(int j = 0; j < num; j++)
            {
                scanf(
"%d"&id);
                g[i][id 
+ m] = INF;
            }
        }
        ans1 
-= ISAP(src, sink, sink + 1);
        printf(
"%d\n", ans1);
        dfs(sink, sink);
        
for(int i = m + 1; i < sink; i++)
        {
            
if(!mark[i])
            {
                ans2[top
++= i - m;
            }
        }
        printf(
"%d", top);
        
for(int i = 0; i < top; i++)
        {
            printf(
" %d", ans2[i]);
        }
        printf(
"\n");
    }
    
return 0;
}
posted on 2010-05-20 10:36 Fucker 阅读(138) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © Fucker Powered by: 博客园 模板提供:沪江博客