題目地址:HDU 5045
終於在比賽中用網絡流A了一道題。。。刷了那麼多網絡流,終於用到一次了。。雖然題目很簡單,但是還是要紀念一下下。。。
我這題的思路就是求m/n次費用流,每n個算作同一輪,對這同一輪的求最大費用流。建圖就很簡單了,最簡單的二分圖模型。
代碼如下:
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 using namespace std; double mp[20][2000], d[200], cost; const int INF=0x3f3f3f3f; int head[200], source, sink, cnt, flow; int f[200], cur[200], vis[200]; struct node { int u, v, cap, next; double cost; } edge[100000]; void add(int u, int v, int cap, double cost) { edge[cnt].v=v; edge[cnt].cap=cap; edge[cnt].cost=cost; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].v=u; edge[cnt].cap=0; edge[cnt].cost=-cost; edge[cnt].next=head[v]; head[v]=cnt++; } int spfa() { int i; for(i=0; i<200; i++) d[i]=INF; memset(vis,0,sizeof(vis)); cur[source]=-1; f[source]=INF; d[source]=0; queueq; q.push(source); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(d[v]>d[u]+edge[i].cost&&edge[i].cap) { d[v]=d[u]+edge[i].cost; f[v]=min(f[u],edge[i].cap); cur[v]=i; if(!vis[v]) { vis[v]=1; q.push(v); } } } } if(d[sink]==INF) return 0; flow+=f[sink]; cost-=f[sink]*d[sink]; for(i=cur[sink]; i!=-1; i=cur[edge[i^1].v]) { edge[i].cap-=f[sink]; edge[i^1].cap+=f[sink]; } return 1; } void mcmf() { cost=flow=0; while(spfa()) ; } int main() { int t, num=0, i, j, k, n, m; double sum; scanf("%d",&t); while(t--) { sum=0; num++; scanf("%d%d",&n,&m); for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { scanf("%lf",&mp[i][j]); } } k=1; sum=0; while(k<=m) { source=0; sink=2*n+1; memset(head,-1,sizeof(head)); cnt=0; for(i=k; i
Codeforces Round #308 (Div. 2)
poj1655 Balancing Act 求樹的重心
單項鏈表的實現,項鏈表實現實現基於單向鏈表的list類。 s
預處理器為我們定義了四個有用的常量,使用這四個常量可以
hdu 5037 Frog(貪心) 分析:貪心吧,讓每次
DM8168 DVR RDK nand系統移植 Nand