acmicpc.net 1671(네트워크 플로우), 2606(플로이드)

https://www.acmicpc.net/problem/1671

상어의 저녁식사. 처음에 그냥 그래프로 모델링해서 냈는데 실패했다.

어떤분이 문제 조건에 있는 a상어가 b상어를 먹고, 먹힌 b상어가 a상어를 다시 먹는 이상한 현상이

발생할수 있다고 해주셔서 생각을 해봤으나 안되서.. 질문했더니 

능력치가 같은 상어가 있을 경우 나중의 상어가 현재의 상어를 못먹게끔 설정해주면 된다고 하셨다.

#include<cstdio>
#include<iostream>
#include<vector>
#include <queue>
using namespace std;
  
const int MAX_X = 2005;
const int MAX_V = 2005;
  
int V;
int capacity[MAX_X][MAX_V], flow[MAX_X][MAX_V];
int ability[MAX_X][3];
  
int networkFlow(int source, int sink) {
    //memset(flow, 0, sizeof(flow));
    for(int i=0;i<MAX_X;i++)
        for(int j=0;j<MAX_V;j++)
            flow[i][j] = 0;
    int totalFlow = 0;
  
    while(true) {
        vector<int> parent(MAX_V, -1);
        queue<int> q;
        parent[source] = source;
        q.push(source);
        while(!q.empty()) {
            int here = q.front(); q.pop();
            for(int there = 0; there < MAX_V; ++there) 
                if(capacity[here][there] - flow[here][there] > 0 && parent[there] == -1) {
                    q.push(there);
                    parent[there] = here;
                }
        }
        if(parent[sink] == -1) break;
        int amount = 2100000000;
        for(int p = sink; p != source; p = parent[p])
            amount = min(amount, capacity[parent[p]][p] - flow[parent[p]][p]);
        for(int p = sink; p != source; p = parent[p]) {
            flow[parent[p]][p] += amount;
            flow[p][parent[p]] -= amount;
        }
        totalFlow += amount;
    }
  
    return totalFlow;
}
  
int main() {
    int E;
    cin >> V;
    for(int i=0;i<MAX_X;i++)
        for(int j=0;j<MAX_V;j++)
            capacity[i][j] = 0;
    for(int i = 0; i < V; ++i) {
        int a;
        capacity[0][i+1] = 2; //한마리당 최대 2마리의 상어 먹을수있다.
        for(int j=0;j<3;j++) //능력치 저장용
        {
            cin >> a;
            ability[i+1][j] = a;
        }
    }
    for(int i=0;i<V;i++)
    {
        for(int j=0;j<V;j++)
        {
            if(i!=j) //상어끼리 비교한다. 다른 상어랑.
            {
                bool flag = true, same = true;
                for(int k=0;k<3;k++) //능력치가 나보다 다 낮은지 확인해서 낮으면
                {
                    if(ability[i+1][k] < ability[j+1][k])
                        flag = false;
		    if(ability[i+1][k] != ability[j+1][k]) //나랑 능력치가 같은지 다른지 확인
			same = false;
                }

                if(flag)
                {
                    capacity[i+1][1000 + j+1] = 1; //먹을수 있는것으로 해놓는다.
                    capacity[1000 + j+1][2003] = 1; //2003이 도착지라고 가정.
                }
		if(same) //나랑 같은놈이면 날 못먹게 한다.
		    capacity[j+1][1000 + i+1] = 0;
            }
        }
    }
    cout << V-networkFlow(0, 2003) << endl;
    //for(int i = 0; i < MAX_V; ++i)
    //    for(int j = 0; j < MAX_V; ++j)
    //        if(flow[i][j] > 0)
    //            cout << i << " => " << j << ": " << flow[i][j] << endl;
}

https://www.acmicpc.net/problem/2606

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
   
int n,m,v,a,b,c;
long long w[102][102];
long long INF = 99999999999;
 
void floyd()
{
    for(int k=1;k<n+1;k++)
        for(int i=1;i<n+1;i++)
            for(int j=1;j<n+1;j++)
                if(w[i][j] > w[i][k]+w[k][j])
                    w[i][j] = w[i][k]+w[k][j];
}
 
      
int main()
{
    ios::sync_with_stdio(false); 
    cin>>n>>m;
    for(int i=1;i<n+1;i++)
        for(int j=1;j<n+1;j++)
            w[i][j] = INF;
 
    for(int i=0;i<m;i++)
    {
        cin>>a>>b;
        w[a][b] = 1;
		w[b][a] = 1;
    }
 
    floyd();
	int virus = 0;

	//for(int i=1;i<n+1;i++)
	//{
	//	for(int j=1;j<n+1;j++)
	//		cout<<w[i][j]<<" ";
	//	cout<<endl;
	//}

	for(int i=2;i<n+1;i++)
	{
		if(w[1][i]!=INF)
			virus++;
	}
	cout<<virus<<"\n";
    return 0;
}